bzoj4566【HAOI2016】找相同字符

#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,n) for(int i=j;i>=n;i--) #define ll long long #define N 200005 #define M 800005 using namespace std; int n,m,cnt=1,last; int fa[M],mx[M],c[M][26],sz[M][2],v[N],q[M]; ll ans; char a[N],b[N]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=⑴;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int d[M]; queue<int> qu; void calc() { // F(i,1,cnt) v[mx[i]]++; // F(i,max(n,m)) v[i]+=v[i⑴]; // F(i,cnt) q[v[mx[i]]--]=i; //这样也是对的 int tmp=cnt; F(i,cnt) d[fa[i]]++; F(i,cnt) if (!d[i]) qu.push(i); while (!qu.empty()) { int x=qu.front();qu.pop(); q[tmp--]=x;d[fa[x]]--; if (!d[fa[x]]) qu.push(fa[x]); } D(i,cnt,1) { sz[fa[q[i]]][0]+=sz[q[i]][0]; sz[fa[q[i]]][1]+=sz[q[i]][1]; } F(i,cnt) ans+=(ll)(mx[i]-mx[fa[i]])*sz[i][0]*sz[i][1]; } void add(int x) { int p=last; if (c[p][x]&&mx[c[p][x]]==mx[p]+1){last=c[p][x];return;} int np=++cnt;last=np; mx[np]=mx[p]+1; while (p&&!c[p][x]) c[p][x]=np,p=fa[p]; if (!p) fa[np]=1; else { int q=c[p][x]; if (mx[q]==mx[p]+1) fa[np]=q; else { int nq=++cnt; mx[nq]=mx[p]+1; memcpy(c[nq],c[q],sizeof(c[q])); fa[nq]=fa[q];fa[q]=fa[np]=nq; while (p&&c[p][x]==q) c[p][x]=nq,p=fa[p]; } } } int main() { scanf("%s",a+1);scanf("%s",b+1); n=strlen(a+1);m=strlen(b+1); last=1;F(i,n) add(a[i]-'a'),sz[last][0]++; last=1;F(i,m) add(b[i]-'a'),sz[last][1]++; calc(); cout<<ans<<endl; return 0; }