3
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks for reply. this is not homework, though. $\endgroup$ – XORwell Aug 5 '14 at 13:37
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.