最长前缀后缀

给定一个字符串，找到最长正确前缀的长度，这也是一个适当的后缀。示例： S = abab则长度为2，前缀='ab'，后缀'ab'是公共的。最长前缀后缀

这是我的代码使用堆栈。它适用于某些情况，而不适用于某些情况。我很难理解为什么它不适用于某些情况。任何人都可以解释我做错了什么？

int main(){ 

long int T,i,j; 

/* total test case */ 
cin>>T>>ws; 

while(T--){ 
string str; 

long int count = 0; 
getline(cin,str); 

stack<char> charStack; 

/** push all character till second last **/ 
for(i=0;i!=str.length()-1;i++){ 
    charStack.push(str[i]); 
} 
j = str.length()-1; 
while(!charStack.empty()){ 

    char ch = charStack.top(); 
    charStack.pop(); 
    if(ch==str[j]){ 

     count++; 
     j--; 
    }else { 

     count = 0; 
     j = str.length()-1; 
    } 




} //inner while 

cout<<count<<"\n"; 


} //outer while 





return 0; 
}

它是失败的测试用例 “khwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhvkhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkgkhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhvkhwkhpkhnkhwkhpkhtkhwrkhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrk hwkhpkhnckhwkhp“

正确的输出是155，而我越来越55。

来源

2016-09-15 randy

您从比较从堆栈（字符串的结束）的顶部字符的字符字符串的结尾（即它们自己），这很奇怪。什么情况下完全失败？ – Ap31

堆栈中的最后一项包含字符串的第二个最后一个字符，而不是最后一个字符。 – randy

问题是，当测试前缀（堆栈）是否匹配后缀时，您将从堆栈中删除整个匹配部分。有时候包括真正最长的前缀的尾部。

我重新count之后加入std::cout << charStack.size() << '\n';，这是输出的相关部分：

正如你所看到的，你从来没有尝试过，以配合前缀长度155。

来源

2016-09-15 21:03:25 user58697

谢谢:)，这清除了我的怀疑 – randy

这里是我的KMP代码： -

#include <bits/stdc++.h> 
using namespace std; 


int main(void){ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
     string s; 
     cin>>s; 
     int n = s.length(); 
     int arr[n]; 
     arr[0] = 0; 
     int len = 0; 
     for(int i = 1;i<n;){ 
      if(s[len]==s[i]){ 
       len++; 
       arr[i++] = len; 
      } 
      else{ 
       if(len!=0){ 
        len = arr[len-1]; 
       } 
       else{ 
        arr[i] = 0; 
        i++; 
       } 
      } 
     } 
     cout<<arr[n-1]<<endl; 
    } 


    return 0; 
}

时间复杂度为O（N）

来源

2018-01-06 16:03:00 HeadAndTail

最长前缀后缀

回答

相关问题