jugal_sahu's blog

new distingct substring (spoj)
By jugal_sahu, 11 years ago, In English

problem link : link

I have already solved distinct substring (spoj : link) but new distinct substring have strict timelimit.Please give me hint.....thanks

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

Comments Comments (10)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Suffix automaton solves this(maybe that is overkill, not sure).

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

You can solve it in O(NlogN) with Suffix Array + Longest Common Prefix Array. Since same substrings will be in adcajent indexes in suffix array, you can easily eliminate them. I mean first calculate the number of same substrings then substract it from (N*(N+1))/2

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

I have solved both actually using java 2 years ago using suffix array and LCP. I used a faster Suffix Array construction to pass the hard one. Do you want it?

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Also counting the paths of a suffix automaton will solve it in linear time.

→ Reply