[文章目录]
Description
计算n个串的最长公共子串。n<=5,len<=2000
STL慢死啦。不过裸过。正常好像都写的hash。
string自带的匹配功能二分长度，每次由于每个串不能重子串，所以扔到set里，在将set扔到multiset里。最后扫一遍multiset计数判断就好了。
本想写hash的，但是突然向检验一下STL的效率。。。不怎么样。600+ms
#include <set>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,len[6];
char st[6][2100];
set<string>s1;
set<string>::iterator it1;
multiset<string>s2;
multiset<string>::iterator it2,it3;
bool check(int x)
{
if(x==0) return true;
s2.clear(); char p;
for(int i=1;i<=n;i++)
{
for(int j=len[i]-x;j>=0;j--)
{
p=st[i][j+x];
st[i][j+x]='\0';
s1.insert(st[i]+j);
st[i][j+x]=p;
}
it1=s1.begin();
while(it1!=s1.end())
s2.insert(*it1),it1++;
s1.clear();
}
it2=s2.begin(); it3=it2;
int cnt=1;
while(it2!=s2.end())
{
it2++;
if(it2!=s2.end()&&*it2==*it3) cnt++;
else
{
if(cnt>=n) return true;
else cnt=1;
}
it3++;
}
return false;
}
int main()
{
scanf("%d",&n);
int l=0,r=2100,mid;
for(int i=1;i<=n;i++)
{
scanf("%s",st[i]);
len[i]=strlen(st[i]);
r=min(len[i],r);
}
r++;
while(l<r)
{
mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
return 0;
}