Given a string, how to get the its prefix similarity? I use an example to explain what I mean by string prefix similarity. Say, s = "ababaa". We take all its suffixes, that is, "ababaa", "babaa", "abaa", "baa", "aa", "a". Then we count their common prefix length with original string. In this case, it is 6 + 0 + 3 + 0 + 1 + 1 = 11.

I hope my question is clear. The straightforward method has complexity $O(n^2)$. Can we do better?

  • 4
    $\begingroup$ Welcome to CS.SE! What have you tried? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Did you try checking whether suffix trees or suffix arrays can be used here? $\endgroup$ – D.W. Oct 14 '16 at 4:35
  • $\begingroup$ @D.W. I tried the $O(n^2)$ method by listing all suffixes and comparing it with the original string. I guess there is way to reuse information just like KMP algorithm. But I could not figure it out. Thanks for pointing out the suffix trees. I will try to look it up. $\endgroup$ – kevin Oct 18 '16 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.