sangshaptac's blog

Help needed on a string problem
By sangshaptac, 12 years ago, In English

i have solved some easy problems on suffix array,i think this problemcan be solved using suffix array,but i am not getting any approach that can suffice the time limit.

Please Help by giving idea on how to solve the problem(preferably by using suffix array)...

Thanks in advance :)

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
12 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

I think you can solve it by KMP(knuth morris pratt) or Z-function algorithm.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it -19 Vote: I do not like it

    If we solve it by KMP it's O(|s|^2) — for each prefix and suffix we find the number of times it occurs in O(|s|).

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +1 Vote: I do not like it

      No, it can be solved in O(|S|).

      First, we just build prefix-function array for S, let's call it pi. If we have pi[i] = x, we not only have prefix of length x ending at position i, but also prefixes of length pi[x - 1], pi[pi[x - 1] - 1] and so on. The number of "good" prefixes for each value of the prefix function can be calculated using DP.

      UPD. Fixed a typo.

      → Reply
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I have solved the question using zFunction... My submission — http://codeforces.me/contest/432/submission/8510013

→ Reply
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

Along with computing suffix array you can compute LCP array (lcp[i] is Longest Common Prefix for adjacent suffixes i and i + 1). Now you can use sparse tables or RangeMinimumQuery to determine how many suffixes have equal prefix of length k.

→ Reply