最長前綴後綴

給定一個字符串，找到最長正確前綴的長度，這也是一個適當的後綴。示例： 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

最長前綴後綴

回答

相關問題