### jigsaw7's blog

By jigsaw7, history, 10 months ago, , Given 2 strings S1 and S2 consisting of English letters.
For each index i in S1, it is required to find the largest index j >= i such that S1[i..j] is a substring of S2.

For example,
S1 = "acdsuaf"
ans = [1, 2, 6, 6, 6, 6, -1].

How to approach this problem in linear time?  Comments (8)
 » Is there a problem link
•  » » Unfortunately, no.
 » i think u can refer geeks for geeks their is a article on it
 » This isn’t the linear time algorithm but binary searching on j will work in O(n log n) which should normally be fast enough for most purposes
•  » » Please explain how to check that S1[i..j] is a substring of S2 in O(1)?
•  » » » You can use hash value of the substring
 » Let $S=S_1+ | +S_2$.Using Suffix Array, construct the LCP array of string $S$. For each suffix of $S_1$, find the maximum LCP with the nearest suffixes of $S_2$ using binary search on the already constructed LCP array of string $S$.Complexity: $O(n log n)$.
 » 10 months ago, # | ← Rev. 2 →   You can you the KMP algorithm to match substring, which has O(n) time complexity.For the rest, use some sort of greedy approach.......I think it should drastically change the runtime.