字符串中的子串计算

对于以下问题，我很难找到比O（n^2）更好的方法。字符串中的子串计算

我给了一个字符串，例如xyxxz。

现在我需要在给定字符串的每个前缀中找到匹配字符的总数。

这里，字符串可能的前缀是：

xyxxz : matching characters is 5 
yxxz : matching characters is 0 (since 1st character doesnt match) 
xxz : matching characters is 1 
xz : matching characters is 1 
z  : matching characters is 0

这应该是输出。我做了下面的代码：

cin>>str; 
len=str.length(); 
for(i=0;i<len;i++){ 
    sum=0; 
    k=i; 
    for(int j=0;j<len;j++) 
    { 
     if(str[k] == str[j]){ 
      sum++; 
      k++; 
     } 
     else 
      break; 
    } 
    cout<<sum<<" "; //I get the output 5 0 1 1 0 
}

但它是为O（n^2）。我想要一个更好的方法：可能是O（n）或O（nlogn）。

在此先感谢。

来源

2012-07-26 vijay

指出'std :: mismatch'，其中IIRC是线性复杂度。 – chris 2012-07-26 04:20:46

这会有所帮助。谢谢@chris :) – vijay 2012-07-26 04:24:49

如果你想要它，[这个页面]（http://en.cppreference.com/w/cpp/algorithm/mismatch）有一个可能的实现。这是一个很好的开始，你可以在哪里改进。 – chris 2012-07-26 04:25:59

int strcoll (register const char *s1, register const char *s2) 
{ 
    while (*s1 == *s2++) { 
     if (*s1++ == '\0') { 
      return 0; 
     } 
    } 
    return *s1 - *--s2; 
}

该函数开始比较每个字符串的第一个字符。如果它们彼此相等，则继续使用以下对，直到字符不同或者直到出现指示字符串末尾的空字符。

返回表示字符串之间关系的整数值：零值表示两个字符串相等。大于零的值表示不匹配的第一个字符在str1中比在str2中有更大的值;而小于零的值表示相反。

来源

2012-07-26 04:42:09 linsek

但它不会给出比O（n^2）更好的解决方案。您必须使用字符串和字符串的每个前缀来执行strcoll。因此，为了得到每个前缀，然后strcoll，它将是O（n^2）。可以用strcmp或str.compare（）完成。 – vijay 2012-07-26 04:45:54

如果为您的字符串构建后缀树，则可以通过后缀树来查找匹配的长度。任何与第一个字符不匹配的根节点的子节点将具有零值，其所有子节点的值都将为零。然后，具有匹配的根节点的子节点的所有后代将至少具有等于该边的匹配长度的匹配。

来源

2012-07-26 04:44:39

这是什么将有所帮助。我需要遍历后缀树，并获得每个前缀的边缘总数，如果我得到你的想法。这将需要O（nlogn）。请纠正我，如果我得到错误。谢谢 – vijay 2012-07-26 04:48:41

@ vjshah：是的，这听起来是对的。由于树可以在O（n）时间内构建，所以它可能比O（n * log（n））做得更好，但我不确定。 – 2012-07-26 04:52:37

是的谢谢你的建议对我很有帮助。 :) – vijay 2012-07-26 04:53:51

我不擅长计算O值..但这里是另一个你需要的实现。我认为它更有效一些。

cin >> str; 

len=str.length(); 
for(i=0;i<len;i++) 
{ 
    sum=0; 
    k=0; 

    while(str[k + sum] == str[i + sum]) 
    { 
      sum++; 
    } 
    cout << sum ; 

}

来源

2012-07-26 05:14:29 ddb

虽然是一个无限循环。而且它又是O（n^2） – vijay 2012-07-26 07:20:21

这可以在线性时间使用以下步骤来完成：

构建后缀数组SA以及LCP的阵列（最长公共前缀数组）。后缀数组是字符串中所有后缀的字典顺序列表（类似于您在示例中给出的列表，但按字典顺序排序。请注意，每个后缀都由其原始字符串中的起始位置表示，即每个后缀一个整数）。 LCP也是一个整数数组，与后缀数组长度相同。在i> 0的每个位置，LCP [i]是后缀数组的第i个后缀与第（i-1）个后缀相同的最长前缀;我们设置LCP [0]：= 0。

可以使用Skew算法（也称为DC算法）以线性时间构造后缀数组，并且可以在O（n）时间内在后缀数组旁边构造LCP数组。有关进一步的想法和实现，请参见SO post on state-of-the-art suffix array algorithms。
确定完整字符串在后缀数组中的位置（例如，通过线性扫描包含整数0的条目的后缀数组）。
从该位置开始沿着LCP阵列向左和向右行进，以识别每个后缀与完整字符串具有相同的最长前缀。我已在this older SO post中详细描述了此过程。

备注虽然这需要不超过O（n）的内存和更多的时间，因此在理论上是最优的，这是一个非常复杂的过程，如果你的字符串是非常长的，只会在实践中非常有用。

来源

2012-07-26 05:24:06 jogojapan

是啊..它似乎很复杂。我的字符串长度为100万。谢谢你的帮助：） – vijay 2012-07-26 07:34:31

使用后缀数组。后缀数组DC3将在O（N）时间内完成，其中N是原始字符串中的字符数。

来源

2013-03-15 05:16:02

字符串中的子串计算

回答

相关问题