# Most frequent $aXa$ substring

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 ?

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.

• thanks for reply. this is not homework, though. Aug 5 '14 at 13:37

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.