0
$\begingroup$

Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l.

Ex.

s = "ab"

l = "defgababajklabe"

The answer here would be 2, because there is "abab" which would be 2 consecutive occurrences of string s in l.

My initial thought was to go through each character in l, and try to match the substring starting at that position with s, if it matched we would increment our count and keep track of some global maximum. We would also set the value of our next starting point to one position after the end of this matched portion.

If at any point there is a mismatch, then we wouldn't have to re-check all the previous characters, we would just go to one position after the start point, that would be our new start point.

For example, when processing the given example, we would eventually set start to index 4 (0 based index), and match ab, then set it to index 6 and match ab again, then set index to 8. At that point there would be a mismatch, and we would just start matching again at index 9. There is no need to start over from index 5.

This is my guess, and it appears to work, but I can't seem to prove why this works. Can someone help me understand why this works? Or doesn't work?

$\endgroup$

2 Answers 2

1
$\begingroup$

You algorithm as described doesn't work. Consider $s=baab$ and $I=\textrm{baabaabbaab}$. Your algorithm would match $s$ with the first $4$ characters of $I$, and since the next $4$ characters don't match $s$, it would then continue with searching $s$ in $I' = aabbaab$.

There is only one occurrence of $s$ in $I'$ causing your algorithm to return $1$ (while the correct answer is $2$).

Here is a solution for your problem that runs in $O(|I|)$ worst-case time. We can safely assume $|s| \le |I|$, as otherwise the answer is trivially $0$.

Step 1. Construct a DFA $D$ for the language of all words that end with $s$. This DFA is essentially a path labelled with the characters in $s$ where the last state is a final state. Additionally, each state has "back-edges" that handle characters different from the (at most one) "forward" edge in the path. These "back-edges" point to the state representing the larger prefix of $s$ that is also a suffix of the string read so far. This sounds more complicated than it really is, and can be computed in linear time (for any constant-size alphabet). Here is an example for $s=\textrm{abba}$ on the alphabet $\{a,b\}$.

enter image description here

Step 2. Now now create an array $A[1, \dots, |I|]$, and feed each character of $I$ to $D$. Whenever $D$ is in the final state after reading the $i$-th character of $I$ set $A[i]$ to $1$, otherwise set $A[i]$ to $0$.

Step 3. Compute the maximum number of consecutive occurrences of $s$ in $I$ using dynamic programming and the array $A$. Define $B[i]$ as the maximum number of contiguous occurrences of $s$ in the prefix $I_i$ consisting of the first $i$ character of $I$, with the additional constraint that the last occurrence in the contiguous sequence must end with the last character of $I_i$. For $i = 0, 1, \dots, |s|-1$ we have $B[i]=0$, while for $i = |s|, \dots, |I|$ we can write: $$ B[i] = \begin{cases} 0 & \mbox{if $A[i]=0$} \\ 1 + B[i-|s|] & \mbox{if $A[i]=1$} \end{cases} = A[i](1+B[i-|s|]). $$

Then the solution to your problem is then $\ell = \max_{i=0, \dots, |I|} B[i]$ and the $\ell$ consecutive occurrences of $s$ start at character number $\arg \max_{i=0, \dots, |I|} B[i] - \ell |s|$ in $I$.

A naive implementation of the dynamic programming algorithm requires time $O(|I|)$ and space $O(|I|)$. However, one can observe that the value stored in $B[i]$ is useless after $B[i+|s|]$ has been computed (except for finding $\ell$). Then, we can replace $B$ with a circular array of length $|s|$ (so that each access to $B[i]$ becomes an access to $B[i \bmod |s|]$) and compute $\ell$ by keeping track of the maximum values of $B[i]$ encountered so far.

Moreover, the array $A$ is not needed as we can run Step 2 and Step 3 in parallel: we feed the $i$-th character of $I$ to $D$ and immediately compute $B[i \bmod |s|]$ depending on whether $D$ is in the final state or not.

With these modifications the algorithm requires $O(|I|)$ time and $O(|s|)$ space.

Finally, notice that we don't really need to explicitly represent $D$: knowing, for each prefix $s'$ of $s$ and each character $c$ of the alphabet, the length of the longest prefix of $s$ that is a suffix of $s \circ c$ is enough (where $\circ$ denotes concatenation). See this chapter from Jeff Erickson's book Algorithms for a way to efficiently compute these quantities.

$\endgroup$
5
  • 1
    $\begingroup$ Perfect, this is a case where it doesn't work. I couldn't think of one. Can you please tell me the correct solution as well? $\endgroup$ Feb 6, 2021 at 5:28
  • $\begingroup$ @Rockstar5645, see the updated answer. $\endgroup$
    – Steven
    Feb 6, 2021 at 16:46
  • $\begingroup$ Thank you very much, after carefully reviewing this answer and using my knowledge of the z algorithm, I was able to cobble together a C++ program that gave me the correct answer for this example. Can you explain how I could programmatically construct the DFA in step 1? Or is this explained in the book you linked? $\endgroup$ Feb 8, 2021 at 1:20
  • $\begingroup$ @Rockstar5645, I'm glad my answer helped! How to implicitly construct the DFA is explained in the chapter I linked in Sections 7.5 and 7.6. $\endgroup$
    – Steven
    Feb 8, 2021 at 1:27
  • $\begingroup$ Got it. I'll go through the chapter. $\endgroup$ Feb 8, 2021 at 1:50
1
$\begingroup$

The string that you are looking for ("maximum number of repetitions of baab") starts with a b obviously. So you can look for a "b" at position x and check if it is followed by "aab". After you found k repeats of the string at positions x to x + 4k-1, you think you could restart the search at position x + 4k. However, there is another b in the search string.

In your particular case, if you found one baab, a longer sequence could start at position x+3. If you found k repeats of baab, since any b at the end of a baab except the last was followed by a b, the string you look for could start at x + 4k - 1.

If the string you search for contains multiple b's, like baabaaab, you would check carefully that the search string can't start at the second b.

$\endgroup$
1
  • $\begingroup$ I'm assuming this would take longer than O(n) where n is the length of the larger string in which we are looking for matches? $\endgroup$ Feb 8, 2021 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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