数据结构
LCT
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;
int n, m, g, x, y, v[N], s[N], p[N], fa[N], son[N][2];
bool NR(int x)
{
return son[fa[x]][0] == x || son[fa[x]][1] == x;
}
bool IRS(int x)
{
return son[fa[x]][1] == x;
}
void push_rev(int x)
{
swap(son[x][0], son[x][1]);
p[x] ^= 1;
return;
}
void push_down(int x)
{
if (p[x])
{
if (son[x][0]) push_rev(son[x][0]);
if (son[x][1]) push_rev(son[x][1]);
p[x] = 0;
}
return;
}
void push_up(int x)
{
s[x] = s[son[x][0]] ^ s[son[x][1]] ^ v[x];
return;
}
void push_hall(int x)
{
if (NR(x)) push_hall(fa[x]);
push_down(x);
}
void rotate(int x)
{
int y = fa[x], z = fa[y], k = IRS(x), g = son[x][!k];
if (NR(y)) son[z][IRS(y)] = x;
if (g) fa[g] = y;
son[x][!k] = y;
son[y][k] = g;
fa[x] = z;
fa[y] = x;
push_up(y);
return;
}
void Splay(int x)
{
push_hall(x);
while(NR(x))
{
if (NR(fa[x]))
{
if (IRS(x) == IRS(fa[x])) rotate(fa[x]);
else rotate(x);
}
rotate(x);
}
push_up(x);
}
void access(int x)
{
for (int y = 0; x; y = x, x = fa[x])
Splay(x), son[x][1] = y, push_up(x);
return;
}
void make_root(int x)
{
access(x);
Splay(x);
push_rev(x);
return;
}
int find_root(int x)
{
access(x);
Splay(x);
while(son[x][0]) push_down(x), x = son[x][0];
Splay(x);
return x;
}
void Split(int x, int y)
{
make_root(x);
access(y);
Splay(y);
return;
}
void link(int x, int y)
{
make_root(x);
if (find_root(y) != x) fa[x] = y;
}
void cut(int x, int y)
{
make_root(x);
if (find_root(y) == x && fa[y] == x && !son[y][0])
{
fa[y] = son[x][1] = 0;
push_up(x);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &v[i]);
while(m--)
{
scanf("%d%d%d", &g, &x, &y);
if (g == 0)
{
Split(x, y);
printf("%d\n", s[y]);
}
else if (g == 1) link(x, y);
else if (g == 2) cut(x, y);
else Splay(x), v[x] = y;
}
return 0;
}
线段树
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,m,u,x,y,z,a[100500];
struct rec
{
ll l,r,num,lazy;
}tree[400500];
ll lazy(ll x){return tree[x].lazy*(tree[x].r-tree[x].l+1);}
void up(ll x)
{
tree[x].num=tree[x*2].num+tree[x*2+1].num+lazy(x*2)+lazy(x*2+1);
return;
}
void make(ll x)
{
if (tree[x].l==tree[x].r)
{
tree[x].num=a[tree[x].l];
return;
}
ll mid=(tree[x].l+tree[x].r)>>1;
tree[x*2].l=tree[x].l,tree[x*2].r=mid;
tree[x*2+1].l=mid+1,tree[x*2+1].r=tree[x].r;
make(x*2);
make(x*2+1);
up(x);
return;
}
void pass(ll x)
{
tree[x*2].lazy+=tree[x].lazy;
tree[x*2+1].lazy+=tree[x].lazy;
tree[x].num+=lazy(x);
tree[x].lazy=0;
return;
}
void change(ll x,ll l,ll r,ll t)
{
if (tree[x].l==l&&tree[x].r==r)
{
tree[x].lazy+=t;
return;
}
if (tree[x].l>=tree[x].r) return;
pass(x);
ll mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid)
{
change(x*2,l,r,z);
up(x);
return;
}
if (l>mid)
{
change(x*2+1,l,r,z);
up(x);
return;
}
change(x*2,l,mid,z);
change(x*2+1,mid+1,r,z);
up(x);
return;
}
ll find(ll x,ll l,ll r)
{
if (tree[x].l==l&&tree[x].r==r)
return tree[x].num+lazy(x);
if (tree[x].l>=tree[x].r) return 0;
pass(x);
ll mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid) return find(x*2,l,r);
if (l>mid) return find(x*2+1,l,r);
return find(x*2,l,mid)+find(x*2+1,mid+1,r);
}
int main()
{
scanf("%lld %lld",&n,&m);
for (int i=1;i<=n;++i)
scanf("%lld",&a[i]);
tree[1].l=1;
tree[1].r=n;
make(1);
for (int i=1;i<=m;++i)
{
scanf("%lld",&u);
if (u==1)
{
scanf("%lld %lld %lld",&x,&y,&z);
change(1,x,y,z);
}
else
{
scanf("%lld %lld",&x,&y);
printf("%lld\n",find(1,x,y));
}
}
}
树状数组
#include<cstdio>
using namespace std;
int n,m,u,x,y,c[500500];
void change(int x,int sum)
{
for (;x<=n;x+=x&-x)
c[x]+=sum;
}
int find(int x)
{
int num=0;
for (;x;x-=x&-x)
num+=c[x];
return num;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
{
scanf("%d",&x);
change(i,x);
}
for (int i=1;i<=m;++i)
{
scanf("%d%d%d",&u,&x,&y);
if (u&1) change(x,y);
else printf("%d\n",find(y)-find(x-1));
}
}
图论
Tarjan
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;
int n, m, x, y, g, w, top, num, tot, ans, d[N], s[N], p[N], deg[N], dfn[N], low[N], head[N];
struct rec
{
int to, next;
}a[N*5];
void add(int x, int y)
{
a[++tot].to = y;
a[tot].next = head[x];
head[x] = tot;
}
void Tarjan(int x)
{
dfn[x] = low[x] = ++num;
d[++top] = x;
for (int i = head[x]; i; i = a[i].next)
{
if (!dfn[a[i].to])
{
Tarjan(a[i].to);
low[x] = min(low[x], low[a[i].to]);
}
else
if (!p[a[i].to])
low[x] = min(low[x], dfn[a[i].to]);
}
if (low[x] == dfn[x])
{
p[x] = ++w;
s[w]++;
while(d[top] != x)
{
s[w]++;
p[d[top]] = w;
top--;
}
top--;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
add(x, y);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
Tarjan(i);
for (int i = 1; i <= n; ++i)
for (int j = head[i]; j; j = a[j].next)
if (p[i] != p[a[j].to])
deg[p[i]]++;
for (int i = 1; i <= w; ++i)
if (!deg[i])
ans = s[i], g++;
if (g == 1) printf("%d", ans);
else putchar(48);
return 0;
}
静态仙人掌
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n, m, w, x, y, z, q, X, Y, ex, ans, tot, tott, b[100010], fa[200010], dep[200010], dis[200010], sum[200010], dfn[200010], low[200010], h[200010], head[200010], f[200010][20];
struct rec
{
ll to, l, next;
}e[2000010], a[2000010];
void add(ll x, ll y, ll z)
{
a[++tot].to = y;
a[tot].l = z;
a[tot].next = head[x];
head[x] = tot;
a[++tot].to = x;
a[tot].l = z;
a[tot].next = head[y];
head[y] = tot;
}
void addd(ll x, ll y, ll z)
{
e[++tott].to = y;
e[tott].l = z;
e[tott].next = h[x];
h[x] = tott;
e[++tott].to = x;
e[tott].l = z;
e[tott].next = h[y];
h[y] = tott;
}
void jh(ll x, ll y, ll z)
{
++ex;
ll pt = y, ss = z;
while(pt != fa[x])
{
sum[pt] = ss;
ss += b[pt];
pt = fa[pt];
}
sum[ex] = sum[x];
sum[x] = 0;
pt = y;
ss = 0;
while(pt != fa[x])
{
ss = min(sum[pt], sum[ex] - sum[pt]);
add(pt, ex, ss);
pt = fa[pt];
}
}
void dfs(ll x)
{
dfn[x] = low[x] = ++w;
for (int i = h[x]; i; i = e[i].next)
if (e[i].to != fa[x])
{
ll v = e[i].to;
if (!dfn[v])
{
fa[v] = x;
b[v] = e[i].l;
dfs(v);
low[x] = min(low[x], low[v]);
}
else low[x] = min(low[x], dfn[v]);
if (low[v] > dfn[x]) add(x, v, e[i].l);
}
for (int i = h[x]; i; i = e[i].next)
if ( dfn[e[i].to] > dfn[x] && fa[e[i].to] != x)
jh(x, e[i].to, e[i].l);
}
void dfs1(int x)
{
dep[x] = dep[f[x][0]] + 1;
for (int j = 1; j <= 16; ++j)
f[x][j] = f[f[x][j - 1]][j - 1];
for (int i = head[x]; i; i = a[i].next)
if (a[i].to != f[x][0])
{
f[a[i].to][0] = x;
if (dis[a[i].to]) dis[a[i].to] = min(dis[a[i].to], dis[x] + a[i].l);
else dis[a[i].to] = dis[x] + a[i].l;
dfs1(a[i].to);
}
}
ll lca(ll x, ll y)
{
if (dep[x] < dep[y]) swap(x, y);
for (int i = 16; i >= 0; --i)
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
for (int i = 16; i >= 0; --i)
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
X = x;
Y = y;
return x == y?x:f[x][0];
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
ex = n;
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d",&x,&y,&z);
addd(x, y, z);
}
dfs(1);
f[1][0] = 1;
dfs1(1);
for (int i = 1; i <= q; ++i)
{
scanf("%d%d",&x,&y);
z = lca(x, y);
if (z <= n) ans = dis[x] + dis[y] - dis[z] - dis[z];
else
{
ans = dis[x] - dis[X] + dis[y] - dis[Y];
if (sum[X] > sum[Y]) swap(X, Y);
ans += min(sum[Y] - sum[X], sum[z] - sum[Y] + sum[X]);
}
write(ans);
}
return 0;
}
最小生成树
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,g,w,x1,y1,ans,dad[5005];
struct rec
{
int x,y,l;
}a[12500005];
int find(int dep){return dad[dep]==dep?dep:dad[dep]=find(dad[dep]);}
bool cmp(rec xx,rec yy)
{
return xx.l<yy.l;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
dad[i]=i;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
{
scanf("%d",&g);
if (i>=j) continue;
a[++w].x=i;
a[w].y=j;
a[w].l=g;
}
sort(a+1,a+1+w,cmp);
for (int i=1;i<=w;++i)
if (find(a[i].x)!=find(a[i].y))
{
x1=find(a[i].x);
y1=find(a[i].y);
dad[min(x1,y1)]=max(x1,y1);
ans+=a[i].l;
}
printf("%d",ans);
}
最短路-Floyd
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,xx,yy;
double f[102][102];
struct rec
{
int x,y;
}a[102];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
scanf("%d",&m);
memset(f,0x7f,sizeof(f));
for (int i=1;i<=m;i++)
{
scanf("%d %d",&xx,&yy);
f[xx][yy]=sqrt(double((a[xx].x-a[yy].x)*(a[xx].x-a[yy].x))+double((a[xx].y-a[yy].y)*(a[xx].y-a[yy].y)));
f[yy][xx]=f[xx][yy];
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if ((i!=j)&&(j!=k)&&(k!=i)&&(f[i][k]+f[k][j]<f[i][j]))
f[i][j]=f[i][k]+f[k][j];
scanf("%d %d",&xx,&yy);
printf("%.2lf",f[xx][yy]);
}
最短路-Dijkstra
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,xx,yy,l;
double f[102][102],b[102],t,maxx;
bool c[102];
struct rec
{
int x,y;
}a[102];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
scanf("%d",&m);
memset(f,0x7f,sizeof(f));
t=f[0][0];
for (int i=1;i<=m;i++)
{
scanf("%d %d",&xx,&yy);
f[xx][yy]=sqrt(double((a[xx].x-a[yy].x)*(a[xx].x-a[yy].x))+double((a[xx].y-a[yy].y)*(a[xx].y-a[yy].y)));
f[yy][xx]=f[xx][yy];
}
scanf("%d %d",&xx,&yy);
for (int i=1;i<=n;i++)
b[i]=f[xx][i];
b[xx]=0;
c[xx]=true;
for (int i=2;i<n;i++)
{
maxx=t;
l=0;
for (int i=1;i<=n;i++)
if ((!c[i])&&(b[i]<maxx))
{
maxx=b[i];
l=i;
}
if (!l) break;
c[l]=true;
for (int i=1;i<=n;i++)
if ((!c[i])&&(b[l]+f[l][i]<b[i]))
b[i]=b[l]+f[l][i];
}
printf("%.2lf",b[yy]);
return 0;
}
最短路-Bellman-Ford
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,xx,yy;
double b[102];
bool pd;
struct rec
{
int x,y;
}a[102];
struct ght
{
int d1,d2;
double jl;
}f[100002];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
scanf("%d %d",&xx,&yy);
f[i].jl=sqrt(double((a[xx].x-a[yy].x)*(a[xx].x-a[yy].x))+double((a[xx].y-a[yy].y)*(a[xx].y-a[yy].y)));
f[i].d1=xx;
f[i].d2=yy;
}
scanf("%d %d",&xx,&yy);
memset(b,0x7f,sizeof(b));
b[xx]=0;
for (int i=1;i<n;i++)
{
pd=false;
for (int j=1;j<=m;j++)
{
if (b[f[j].d1]+f[j].jl<b[f[j].d2]) b[f[j].d2]=b[f[j].d1]+f[j].jl,pd=true;
if (b[f[j].d2]+f[j].jl<b[f[j].d1]) b[f[j].d1]=b[f[j].d2]+f[j].jl,pd=true;
}
if (!pd) break;
}
printf("%.2lf",b[yy]);
}
最短路-SPFA
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
int n,m,x,y,a[102],b[102],M,s[102],g;
double v[102];
bool p[102];
struct rec
{
int next,to;
double l;
}f[1002];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d %d",&a[i],&b[i]);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
f[++M].l=sqrt(double((a[x]-a[y])*(a[x]-a[y]))+double((b[x]-b[y])*(b[x]-b[y])));
f[M].to=y;
f[M].next=s[x];
s[x]=M;
f[++M].l=f[M-1].l;
f[M].to=x;
f[M].next=s[y];
s[y]=M;
}
queue<int> d;
scanf("%d %d",&x,&y);
memset(v,0x7f,sizeof(v));
d.push(x);
p[1]=true;
v[x]=0;
while(!d.empty())
{
g=d.front();
d.pop();
for (int i=s[g];i;i=f[i].next)
if (v[g]+f[i].l<v[f[i].to])
{
v[f[i].to]=v[g]+f[i].l;
if (!p[f[i].to])
{
p[f[i].to]=true;
d.push(f[i].to);
}
}
p[g]=false;
}
printf("%.2lf",v[y]);
}
数学&数论
FFT
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1000010
using namespace std;
const double Pi=acos(-1);
int n,m,r[N<<2];
struct CP
{
CP(double xx=0,double yy=0){x=xx,y=yy;}
double x,y;
CP operator +(CP const &b)const
{return CP(x+b.x,y+b.y);}
CP operator -(CP const &b)const
{return CP(x-b.x,y-b.y);}
CP operator *(CP const &b)const
{return CP(x*b.x-y*b.y,x*b.y+y*b.x);}
}f[N<<2],g[N<<2];
void fft(CP *f,int flag)
{
for(int i=0;i<n;++i)
if(i<r[i])swap(f[i],f[r[i]]);
for(int p=2;p<=n;p<<=1){
int len=p>>1;
CP G(cos(2*Pi/p),sin(2*Pi/p)*flag);
for(int k=0;k<n;k+=p){
CP buf(1,0);
for(int i=k;i<k+len;++i){
CP g=buf*f[i+len];
f[i+len]=f[i]-g;
f[i]=f[i]+g;
buf=buf*G;
}
}
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;++i)scanf("%lf",&f[i].x);
for(int i=0;i<=m;++i)scanf("%lf",&g[i].x);
for(m+=n,n=1;n<=m;n<<=1);
for(int i=0;i<n;++i)
r[i]=(r[i>>1]>>1)|(i&1?n>>1:0);
fft(f,1);
fft(g,1);
for(int i=0;i<n;++i)f[i]=f[i]*g[i];
fft(f,-1);
for(int i=0;i<=m;++i)printf("%d ",(int)(f[i].x/n+0.5));
return 0;
}
矩阵乘法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define wyc 1000000007
ll n;
struct matrix
{
ll n, m, a[5][5];
matrix operator *(const matrix b) const
{
matrix c;
c.n = n;
c.m = b.m;
for (ll i = 1; i <= c.n; ++i)
for (ll j = 1; j <= c.m; ++j)
c.a[i][j] = 0;
for (ll i = 1; i <= n; ++i)
for (ll k = 1; k <= m; ++k)
for (ll j = 1; j <= b.m; ++j)
c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % wyc) % wyc;
return c;
}
}A, B;
void ksm(ll g)
{
while(g)
{
if (g & 1) A = A * B;
B = B * B;
g>>=1;
}
}
int main()
{
scanf("%lld", &n);
B.n = 2;
B.m = 2;
B.a[1][1] = 0;
B.a[1][2] = 1;
B.a[2][1] = 1;
B.a[2][2] = 1;
A.n = 1;
A.m = 2;
A.a[1][1] = 1;
A.a[1][2] = 1;
ksm(n - 1);
printf("%lld", A.a[1][1]);
return 0;
}
线性筛素数
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, q, x, w, prime[6000000];
bool p[100000010];
void work(int n)
{
for (int i = 2; i <= n; ++i)
{
if (!p[i]) prime[++w] = i;
for (int j = 1; j <= w && i * prime[j] <= n; ++j)
{
p[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
return;
}
int main()
{
scanf("%d%d", &n, &q);
work(n);
for (int i = 1; i <= q; ++i)
{
scanf("%d", &x);
printf("%d\n", prime[x]);
}
return 0;
}
字符串
Trie
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1000100
using namespace std;
int n, m, w, a[N], to[N][30];
char s[N];
void insert(char* s)
{
int n = strlen(s+1), x = 0, y;
for (int i = 1; i <= n; ++i)
{
y = s[i] - 'a';
if (!to[x][y]) to[x][y] = ++w;
x = to[x][y];
}
a[x]++;
return;
}
int ask(char* s)
{
int n = strlen(s+1), x = 0, y, ans = 0;
for (int i = 1; i <= n; ++i)
{
y = s[i] - 'a';
if (to[x][y]) x = to[x][y];
else return ans;
ans += a[x];
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s+1);
insert(s);
}
while(m--)
{
scanf("%s", s+1);
printf("%d\n", ask(s));
}
return 0;
}
KMP
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define N 1000100
using namespace std;
int nx[N];
char s[N], str[N];
void gnx(char* s) {
int n = strlen(s + 1);
for (int i = 2, j = 0; i <= n; ++i) {
while (s[i] != s[j + 1] && j) j = nx[j];
if (s[i] == s[j + 1])
j++;
nx[i] = j;
}
return;
}
int match(char* s, char* str) {
int n = strlen(s + 1), m = strlen(str + 1), ans = 0;
for (int i = 1, j = 0; i <= m; ++i) {
while ((j == n || str[i] != s[j + 1]) && j) j = nx[j];
if (str[i] == s[j + 1])
j++;
if (j == n)
ans++;
}
return ans;
}
int main() {
scanf("%s%s", str + 1, s + 1);
gnx(s);
printf("%d", match(s, str));
return 0;
}
hash
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;
int n, l, ans;
ull x[10010];
char s[1510];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s+1);
l = strlen(s+1);
for (int j = 1; j <= l; ++j)
x[i] = x[i] * 131llu + s[j];
}
sort(x + 1, x + 1 + n);
for (int i = 1; i <= n; ++i)
if (x[i] != x[i - 1] || i == 1) ans++;
printf("%d", ans);
return 0;
}
Manacher
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 110000010
using namespace std;
int n, ans, l[N*2], s[N*2];
string str;
void Manacher()
{
int mid = 0, mx = 0;
for (int i = 1; i <= n; ++i)
{
if (i < mx) l[i] = min(l[mid * 2 - i], mx - i);
else l[i] = 1;
while(s[i + l[i]] == s[i - l[i]]) l[i]++;
if (i + l[i] > mx)
{
mid = i;
mx = i + l[i];
}
ans = max(ans, l[i]);
}
return;
}
int main()
{
cin>>str;
n = str.size();
s[0] = s[1] = '#';
for (int i = 1; i <= n; ++i)
{
s[i * 2] = str[i - 1];
s[i * 2 + 1] = '#';
}
n = n * 2 + 2;
s[n] = 0;
Manacher();
printf("%d", ans - 1);
return 0;
}
AC自动机
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 20100
using namespace std;
int n, w, ans, a[200], v[N], nx[N], to[N][30];
char s[200][100], ss[1000100];
queue<int>d;
void insert(char* s, int g)
{
int n = strlen(s+1), now = 0, y;
for (int i = 1; i <= n; ++i)
{
y = s[i] - 'a';
if (!to[now][y]) to[now][y] = ++w;
now = to[now][y];
}
v[now] = g;
return;
}
void bfs()
{
for (int i = 0; i < 26; ++i)
if (to[0][i]) d.push(to[0][i]);
while(!d.empty())
{
int h = d.front();
d.pop();
for (int i = 0; i < 26; ++i)
if (!to[h][i]) to[h][i] = to[nx[h]][i];
else nx[to[h][i]] = to[nx[h]][i], d.push(to[h][i]);
}
return;
}
void ask(char* s)
{
int n = strlen(s+1), now = 0, y, g;
for (int i = 1; i <= n; ++i)
{
y = s[i] - 'a';
now = g = to[now][y];
while(g)
{
if (v[g]) a[v[g]]++;
g = nx[g];
}
}
return;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s[i]+1);
insert(s[i], i);
}
bfs();
scanf("%s", ss+1);
ask(ss);
for (int i = 1; i <= n; ++i)
ans = max(ans, a[i]);
printf("%d\n", ans);
for (int i = 1; i <= n; ++i)
if (a[i] == ans)
printf("%s\n", s[i]+1);
return 0;
}
PAM
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 500010
using namespace std;
int n,k,last;
char s[N];
struct PAM
{
int nm,now,c[N],len[N],num[N],fail[N],to[N][30];
void pre_work()
{
now=1;
len[1]=-1;
fail[0]=1;
c[0]=-1;
last=0;
return;
}
int get_fail(int x)
{
while(c[nm]!=c[nm-len[x]-1])x=fail[x];
return x;
}
void add(int x)
{
c[++nm]=x;
int ls=get_fail(last);
if(!to[ls][x]){
len[++now]=len[ls]+2;
fail[now]=to[get_fail(fail[ls])][x];
to[ls][x]=now;
num[now]=num[fail[now]]+1;
}
last=to[ls][x];
}
}T;
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
T.pre_work();
for(int i=1;i<=n;++i){
s[i]=(s[i]-97+k)%26;
T.add(s[i]);
k=T.num[last];
printf("%d ",k);
}
return 0;
}
|