Define Qi(S) as the length of the longest substring that starts at position i an
ID: 3720732 • Letter: D
Question
Define Qi(S) as the length of the longest substring that starts at position i and matches a suffix of S starting at some position not equal to i. For example, in the string S = rzbaaaxpdqbaaax, Q3 = 5. Show how to compute all the Q values (that is for all the i) in O(|S|) time. This is not as obvious as it looks. It is not true that you just reverse S and compute the Z values. But if you try that idea and see why it fails, you will probably next see the right idea.
This doesn't need to be in any specific programming language. Rather, just give a high-level explanation of how the algorithm would work in english.
Explanation / Answer
Solution
let us have two pointers m and n , m is for the string starting at position i and n is for traversing the rest of the string.
initialize n = i + 1
and m = i
also keep two counters count and MAX
initialize count = 0 and MAX = 0
algorithm
loop till n!=|S| {
compare S[m] and S[n]
if equal {
count=count+1
MAX=max(count,MAX)
m=m+1
}
else {
if(count !=0){
m=i
count=0
n=n-1
}
}
n=n+1
}
-------
the basic idea of the algorithm is to loop till you find the first letter matching and then increment the value of m pointer to see whether the next character is also matching and so on(and keep on updating count). when the character doesn't match there are two cases. one that it was the first character that did not match in which case count was already zero and we just increment n and move on but if the first character has already matched and we are matching.. say maybe the third or fourth character (count is 3 or 4) then we should not increment n (that is why i did n = n-1 in the if block, there is always a n = n + 1 at the end which will cancel it out) in case it does not match because we have to compare it to the first character again and decrement m to 0 (so that we can again start comparing from the first letter itself). The complexity is O(|S|).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.