问题描述

poj 1226我的代码为什么wa，求hack，给出测试数据，或者思路的错误

代码如下：
//#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 105;
int next[maxn];
int ans[maxn];
string s[maxn];
void getnext(string a)
{
int i = 0;int j = -1;
next[0] = -1;
while(i<a.length()){
if(j == -1||a[i] == a[j])
{
i++;j++;
next[i] = j;
}
else
j = next[j];
}
}
int kmp(string a,string b){
getnext(a);
int ans = 0;
int al = a.size();
int bl = b.size();
//cout<<b<<endl;
int i = 0;int j = 0;
while(i<bl){
if(j == -1||a[j] == b[i]){
//cout<<i<<" "<<j<<a[j]<<b[i]<<endl;
i++;j++;

    }
    else{
        j = next[j];
    }
     ans = max(ans,j);
    if(j == al)
        j = next[j];
}
return ans;

}
string jianyi(string a){
string b = a;
reverse(b.begin(),b.end());
b = b.substr(0,b.size()-1);
reverse(b.begin(),b.end());
return b;
}
int main() {
int T;
cin>>T;
while(T--){
memset(ans,0x3f,sizeof(ans));
int n;
cin>>n;
if(n == 0) {cout<<"0"<
if(n == 1){
cin>>s[0];
cout<
continue;
}
int mini = 0;
int minsize = 0x3f3f3f;
for(int i = 0;i
cin>>s[i];
if(s[i].size()<minsize)
{
minsize = s[i].size();
mini = i;
}
}
string a = s[mini];
string b = a;
reverse(b.begin(),b.end());

    for(int i = 0;i<s[mini].length();i++){
        for(int j = 0;j<n;j++){
                if(j == mini)continue;
               // cout<<i<<" "<<kmp(a,s[j])<<" "<<kmp(b,s[j])<<endl;
            ans[i] = min(ans[i],max(kmp(a,s[j]),kmp(b,s[j])));
        }
       // cout<<ans[i]<<endl;
       a = jianyi(a);
       b =  jianyi(b);
    }
    int ant = 0;
    for(int i = 0;i<s[mini].length();i++){
            //cout<<ans[i];
        ant = max(ant,ans[i]);
    }
    cout<<ant<<endl;
    }

return 0;

}

解决方案

http://bbezxcy.iteye.com/blog/1407379
http://blog.csdn.net/xingyeyongheng/article/details/9274461