给你两个4k长度的串，问你最长公共子串。两个子串相同被定义为所有字母的出现次数分别相同即可。
就枚举第一个串的所有子串，将字母出现的次数看作一个大数，进行哈希（双关键字），塞到哈希表里面。然后枚举第二个串的子串，去哈希表里面查即可。
一开始用的map，空间被卡常数了。
后来问了别人，发现set就能过，没必要用哈希表。
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
typedef unsigned int uin;
typedef unsigned long long ull;
const uin MOD1=2000000011;
const uin MOD2=1000000033;
const uin MOD=8002003;
const uin MODD=8004011;
struct HashTable
{
uin v[MOD];
int en,first[MOD],next[MOD],w[MOD];
HashTable(){en=0;memset(first,-1,sizeof(first));}
void insert(const uin &V,const int &W)
{
int U=(int)(V%MOD);
v[en]=V;
w[en]=W;
next[en]=first[U];
first[U]=en++;
}
int query(const uin &V)
{
int U=(int)(V%MOD),res=0;
for(int i=first[U];i!=-1;i=next[i])
if(v[i]==V){
return w[i];
}
return 0;
}
}T;
struct HashTable2
{
uin v[MODD];
int en,first[MODD],next[MODD],w[MODD];
HashTable2(){en=0;memset(first,-1,sizeof(first));}
void insert(const uin &V,const int &W)
{
int U=(int)(V%MODD);
v[en]=V;
w[en]=W;
next[en]=first[U];
first[U]=en++;
}
int query(const uin &V)
{
int U=(int)(V%MODD),res=0;
for(int i=first[U];i!=-1;i=next[i])
if(v[i]==V){
return w[i];
}
return 0;
}
}T2;
char a[4010],b[4010];
int n,m,ans;
uin pow1[4010],pow2[4010];
int main(){
pow1[0]=pow2[0]=1;
for(int i=1;i<=4000;++i){
pow1[i]=(uin)((ull)pow1[i-1]*(ull)10007%(ull)MOD1);
pow2[i]=(uin)((ull)pow2[i-1]*(ull)10009%(ull)MOD2);
}
scanf("%s%s",a+1,b+1);
n=strlen(a+1);
m=strlen(b+1);
for(int i=1;i<=n;++i){
uin hs1=0,hs2=0;
for(int j=i;j<=n;++j){
hs1=(uin)(((ull)hs1+(ull)pow1[a[j]-'a'])%(ull)MOD1);
hs2=(uin)(((ull)hs2+(ull)pow2[a[j]-'a'])%(ull)MOD2);
// ma[make_pair(hs1,hs2)]=j-i+1;
T.insert(hs1,j-i+1);
T2.insert(hs2,j-i+1);
}
}
for(int i=1;i<=m;++i){
uin hs1=0,hs2=0;
for(int j=i;j<=m;++j){
hs1=(uin)(((ull)hs1+(ull)pow1[b[j]-'a'])%(ull)MOD1);
hs2=(uin)(((ull)hs2+(ull)pow2[b[j]-'a'])%(ull)MOD2);
// ans=max(ans,ma[make_pair(hs1,hs2)]);
int tmp=T.query(hs1);
if(tmp==T2.query(hs2)){
ans=max(ans,tmp);
}
}
}
printf("%d
",ans);
return 0;
}