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?

  • 3
    $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.