最長接頭辞

Question

文字列を指定すると、適切な最長の接頭辞の長さが適切な接尾辞にもなります。 例： S = abab長さは接頭辞= 'ab'として2になり、接尾辞 'ab'は共通です。

ここで私のコードはスタックを使用しています。それはいくつかのケースではなく、いくつかのケースで動作しています。私は、なぜそれがいくつかのケースのために働いていない理由を理解するのに苦労している。誰も私が間違っていることを説明することはできますか？これは、テストケース 「khwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhvkhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkgkhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhvkhwkhpkhnkhwkhpkhtkhwrkhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkhwkhpkhnckhwkhpkhnkhwkhpkhtkhwkhpkhnkhdkhwkhpkhnkhwkhpkhtkhokhwkhpkhnkhwkhpkhtkhwkhpkhnkhwkhfkhwkhrkのために失敗している

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; 
} 

hwkhpkhnckhwkhp "

私は55を取得している間、正しい出力は155です。

Answer 1

問題は、接頭辞（スタック）が接尾辞と一致するかどうかをテストするときに、スタックから一致する部分全体を削除することです。時には真に最長のプレフィックスの末尾も含まれます。

私は右countをリセットした後std::cout << charStack.size() << '\n';を追加し、これは、出力の関連する部分である：

212 
211 
154 
153 

あなたが見ることができるように、あなたはプレフィックス長155に合わせて試したことがありません。

ここ

Answer 2

MY 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）