Question

HDU 1238 一直WA，找不到错误？样例都过了 代码如下：

#include<iostream>
#include<string>
using namespace std;
bool index(string s,string t) //t为匹配字符串
{
int i=s.find(t);
int j;
if(i!=-1) return true;
else {
string w="";
for(int j=t.length()-1;j>=0;j--)
{
w+=t[j];
}
i=s.find(w);
}
if(i!=-1) return true;
else return false;
}
int main()
{
int t;
cin>>t;
while(t--)
{
string str[110];
int n;
cin>>n;
int i;
int min=9999999,length;
for(i=0;i<n;i++) //求子串，并记录最短的字符串
{
cin>>str[i];
if(str[i].size()<min) {min=str[i].size();length=i;}
}
string sub[1000];//保存子串
int k=0,j,ans=0,flag=1;
for(i=0;i<str[length].size();i++) //求最短字符串的所有子串
for(j=1;j<=str[length].size()-i;j++)
sub[k++]=str[length].substr(i,j);
for(i=0;i<k;i++) //遍历所有子串
{
flag=1;
if(sub[i].length()>ans){
for(j=0;j<n;j++) //遍历每个字符串
if(index(str[j],sub[i])==false) {flag=0;break;}
if(flag==1) ans=sub[i].size();
}
}
cout<<ans<<endl;
}
return 0;
}

Answer 1

/*
搜索入门题
对字符串按长度进行排序
然后对最短的字符串枚举所有的子串
用到了 求反串 求子串 字符串查找
*/

【AC源代码】

#include<iostream>
#include<string>
using namespace std;
string sou[150];
int t,n;
bool cop(string a,string b)
{
return a.size()<b.size();
}
string inverse(string a)/*求反串*/
{
int tlen=a.size();
string t;
for(int i=tlen-1;i>=0;i--)
{
t.append(1,a[i]);
}
return t;
}
int len(string a)/*对字符串进行枚举子串和查找答案*/
{
int t=a.size();
for(int i=t;i>=1;i--)
{
for(int j=0;j+i<=t;j++)
{
string tmp=a.substr(j,i);
string rtmp=inverse(tmp);
int ok=1;
for(int k=1;k<n;k++)
{
if(sou[k].find(tmp)!=-1)
continue;
if(sou[k].find(rtmp)!=-1)
continue;
ok=0;
break;
}
if(ok)return tmp.size();
}
}
return 0;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>sou[i];
}
sort(sou,sou+n,cop);/*字符串排序*/
int ans=len(sou[0]);
cout<<ans<<endl;
}
return 0;
}

追问

那你能不能帮我的代码AC了。我的思路跟你是一样的。
暴力枚举