<p>We get to cheat a little bit more, actually.</p>

<p>Let $k=|\Sigma|$</p>

<p>If $q = aXbYbZa$ is a pattern, then $bYb$ occurs at least as many times as $q$.  Thus, we only need to find patterns $cWc$ where $W$ contains no repeats and does not contain $c$.  This means that the length of $q$ is at most $k+1$</p>

<p>We are going to build a trie-like structure where each node contains the number of times the string representing that node has been seen.</p>

<pre>
for i: each index of s
    simultaneously insert s[i:i],s[i:i+1],...,s[i:i+k] into the trie by
    inserting s[i:i+k] but incrementing the count on each node while descending the trie

traverse the trie
    keep track of the node with the highest count which represents a string of the form aXa
reproduce the string with the highest count from the trie and return it
</pre>

<p>The running time for this is $O(kn)$.  While building the trie, we touch $k$ nodes for each index of $s$.  The trie has only $O(kn)$ nodes, so traversing it takes only $O(kn)$ time.</p>

CC BY-SA 3.0
2014-09-05T14:48:17.403Z
2014-09-05T14:48:17.403Z
bbejot
<p>Yes, you can solve the problem using standard techniques. However, the question may easily be homework, so here is just a hint:</p>

<p>You never need to consider words of the form $aXaYa$, as they cannot be the only most frequent ones.</p>

CC BY-SA 3.0
2014-08-05T13:37:04.377Z
thanks for reply. this is not homework, though.
XORwell
CC BY-SA 3.0
2014-08-05T10:43:01.117Z
2014-08-05T10:43:01.117Z
DCTLib
<p>Let $s\in\Sigma^*$ be a string, for some alphabet $\Sigma$.
We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent repeated substring of type $q=aXa$ for $a\in\Sigma, X\in \Sigma^*$.</p>

<p>Can we solve this problem with standard techniques ? I'm thinking about suffix-trees here. What is the most efficient algorithm for this problem ?</p>

<ds.algorithms><string-matching>
Most frequent $aXa$ substring
XORwell
# Most frequent $aXa$ substring

(Asked by: username_0 on 2014-08-05)

Let $s\in\Sigma^\*$ be a string, for some alphabet $\Sigma$.
We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent repeated substring of type $q=aXa$ for $a\in\Sigma, X\in \Sigma^\*$.

Can we solve this problem with standard techniques ? I'm thinking about suffix-trees here. What is the most efficient algorithm for this problem ?

**Tags:** ds.algorithms, string-matching


---

## 2 answers

### Answer by username_1 on 2014-09-05. Score: 1

We get to cheat a little bit more, actually.
Let $k=|\Sigma|$
If $q = aXbYbZa$ is a pattern, then $bYb$ occurs at least as many times as $q$.  Thus, we only need to find patterns $cWc$ where $W$ contains no repeats and does not contain $c$.  This means that the length of $q$ is at most $k+1$
We are going to build a trie-like structure where each node contains the number of times the string representing that node has been seen.

for i: each index of s
    simultaneously insert s[i:i],s[i:i+1],...,s[i:i+k] into the trie by
    inserting s[i:i+k] but incrementing the count on each node while descending the trie

traverse the trie
    keep track of the node with the highest count which represents a string of the form aXa
reproduce the string with the highest count from the trie and return it

The running time for this is $O(kn)$.  While building the trie, we touch $k$ nodes for each index of $s$.  The trie has only $O(kn)$ nodes, so traversing it takes only $O(kn)$ time.


---

### Answer by username_2 on 2014-08-05. Score: 1

Yes, you can solve the problem using standard techniques. However, the question may easily be homework, so here is just a hint:

You never need to consider words of the form $aXaYa$, as they cannot be the only most frequent ones.

> **Comments:**
> **username_0**: thanks for reply. this is not homework, though.  

---

