0.04卡常
查看原帖
0.04卡常
186045
itisover楼主2021/10/18 21:49

T了0.04s,实测快读没什么用,是ull的sort太慢了吗?

#include<bits/stdc++.h>
using namespace std;
const int N=3005,bas=29;
int n,L[N][26],cnt;
char s[N],t[N];
unsigned long long H[N],base[N],a[N*N];
unsigned long long Hs(int l,int r){return H[r]-H[l-1]*base[r-l+1];}
int main(){
    scanf("%d%s%s",&n,s+1,t+1);
    base[0]=1;
    for(int i=1;i<=n;++i) H[i]=H[i-1]*bas+t[i],base[i]=base[i-1]*bas;
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            if(!L[i][s[j]-'a']) L[i][s[j]-'a']=j+1;
    for(int i=1;i<=n;++i)
        for(int j=i,p=1;j<=n;++j){
            if(L[p][t[j]-'a']) p=L[p][t[j]-'a'],a[++cnt]=Hs(i,j);
            else break;
        }
    sort(a+1,a+1+cnt);
    printf("%d",unique(a+1,a+1+cnt)-a-1);
    return 0;
}
2021/10/18 21:49
加载中...