arif.ozturk's blog

Longest common prefix question
By arif.ozturk, history, 6 years ago, In English

Hello, I recently got an interesting question from my old teacher. Given two strings A and B(of size <=2000000) find the sum of the longest common prefixes of A and all substrings of B. I reduced this to finding the longest common prefix of A and all suffixes of B and found a solution in O(NlogN) time using suffix arrays. Because it consumed a lot of memory, I switched to hashing and it worked to some extent but it seems O(NlogN) is too large as I get TLE. I was thinking whether I could change the KMP algorithm a bit to get exactly what I need but I can't seem to find a way. Do you guys have any ideas?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can concatenate A and B and run Z-function on it. In O(n+m) you get want you want (length of LCP for all suffix of B)

→ Reply