所有子字符串和一个字符串的最长公共前缀长度 [英] Longest common prefix length of all substrings and a string

问题描述

我在StackOverflow上发现了类似的问题，但是我的问题有所不同。

I found similar questions on StackOverflow, but my question is different.

给出一个字符串 s 包含小写字母字母。我想找到所有子字符串中最长公共前缀的长度。

Given a string s contains lowercase alphabet. I want to find the length of Longest common Prefix of all substrings.

例如

s = 'ababac'

然后子串如下：

1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c

现在，所有子字符串的 LCP 的长度如下

Now, The lengths of LCP of all substrings are as follow

1: len(LCP(s(1, 6), s)) = 6 
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

我正在使用逐字符匹配

    string commonPrefix(string s1, string s2) { 
        int minlen = minlength1(s1, s2); 
        char current; 
        int result = 0;
        for (int i=0; i<minlen; i++) { 
            current = s1[i]; 
            for (int j=1 ; j<n; j++) 
                if (s2[i] != current) 
                return result; 
            result++;
        } 

        return result; 
    }

但是，它仍然是O（n2）。我知道所有子串都相互重叠，可以进一步优化。有人可以帮助优化此代码吗？

But still, it's O(n2). I know all substrings are overlapping on one another, It can be optimized further. Can anyone help to optimize this code?

推荐答案

正如Aditya所述，可以使用Z-算法来解决。请在此处找到实施的详细说明- https：// www.hackerearth.com/practice/algorithms/string-algorithm/z-algorithm/tutorial/

As mentioned by Aditya, this can be solved using Z-Algorithm. Please find the detailed explanation with implementation here - https://www.hackerearth.com/practice/algorithms/string-algorithm/z-algorithm/tutorial/

这篇关于所有子字符串和一个字符串的最长公共前缀长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！