KMP 和 AC 自动机都只会背板子怎么办啊 /kk。
模板
AC 自动机
不会，但我会背板子。
for(int i=0;i<26;i++) ch[0][i]=1;
queue<int> q;q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
if(!ch[u][i]) ch[u][i]=ch[fail[u]][i];
else fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
}
马拉车
\(O(n)\) 求出一个字符串每个位置 \(i\) 最大的 \(r_i\)，使得 \([i-r_i+1,i+r_i-1]\) 是回文串。
考虑到一个可能有长度为偶数的回文串，不好搞，我们在每个字符前后都加上一个特殊字符，比如 #。
原串：
abbaba加入后：
#a#b#b$a$b#a#
这样我们只用考虑 \(i\) 作为唯一一个回文中心的情况。
记一个位置 \(p,p<i\)，使得 \(R=p+r_p\) 最大。
如果 \(i <R\)，
我们找到 \(i\) 关于 \(p\) 的对称点 \(i'\)。
然后继承 \(r_{i'}\)。并看能否继续拓展。
如图：
否则初始 \(r_i=0\) 然后拓展。
可以发现拓展的时候 \(R\) 始终会增大，所以是 \(O(n)\) 的。
对于边界问题，在字符串边界插入一对不相同的特殊字符即可。
s[++m]='!',s[++m]='#';for(int i=1;i<=n;i++) s[++m]=c[i],s[++m]='#';s[++m]='?';
for(int i=2;i<m;i++)
{
if(i<=R) r[i]=min(r[p*2-i],R-i+1);
while(s[i-r[i]]==s[i+r[i]]) r[i]++;
if(i+r[i]>R) R=i+r[i]-1,p=i;
}
题目
P2414 阿狸的打字机
可以发现一个结论：
对于 AC 自动机上的一个结点 \(u\)，设其对应的字符串为 \(S_u\)，那么 \(S_{fail_u}\) 是 \(S_{u}\) 的子串。
于是建出失配树（连边 \(fail_u \rightarrow u\)），那么 \(u\) 子树内所有结点对应的串都包含 \(S_u\)。
对于一组询问 \((x,y)\)，设串 \(S_x\) 的结束结点为 \(u\)，问题转化为在失配树上 \(u\) 的子树内有多少 \(y\) 的结点。
离线后把询问挂到 \(y\) 对应的 trie 树的结束结点上，遍历 trie 树的同时维护树上差分。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char c;
int n,m,dn,tot=1,u=1;
int l[N],r[N],id[N],ch[N][26],trie[N][26],fa[N],fail[N],ans[N];
vector<int> G[N],ed[N];
vector<pair<int,int>> q[N];
struct BIT{
int c[N];
void upd(int x,int v) {for(;x<=dn;x+=x&-x) c[x]+=v;}
int qsum(int x) {int r=0;for(;x;x^=x&-x) r+=c[x];return r;}
}tr;
void build()
{
memcpy(trie,ch,sizeof(ch));
for(int i=0;i<26;i++) ch[0][i]=1;
queue<int> q;q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
G[fail[u]].push_back(u);
for(int i=0;i<26;i++)
if(!ch[u][i]) ch[u][i]=ch[fail[u]][i];
else fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
}
}
void dfs(int u)
{
l[u]=++dn;
for(int v:G[u]) dfs(v);
r[u]=dn;
}
void solve(int u)
{
tr.upd(l[u],1);
for(int i:ed[u]) for(auto [x,j]:q[i]) ans[j]=tr.qsum(r[id[x]])-tr.qsum(l[id[x]]-1);
for(int i=0;i<26;i++) if(trie[u][i]) solve(trie[u][i]);
tr.upd(l[u],-1);
}
int main()
{
while((c=getchar())!='\n')
{
if(c=='P') ed[u].push_back(++n),id[n]=u;
else if(c=='B') u=fa[u];
else {c-='a';if(!ch[u][c]) ch[u][c]=++tot;fa[ch[u][c]]=u,u=ch[u][c];}
}
build();dfs(0);
cin>>m;
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
q[y].push_back({x,i});
}
solve(1);
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}
CF1207G Indie Album
同样的套路。
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,tot=1,dn,ch[N][26],fail[N],ans[N],id[N];
char c[N],s[N];
vector<int> G[N],Tf[N],q[N];
struct BIT{
int c[N];
void upd(int x,int v) {for(;x<=dn;x+=x&-x) c[x]+=v;}
int qsum(int x) {int r=0;for(;x;x^=x&-x) r+=c[x];return r;}
}tr;
void insert(int i)
{
int n=strlen(s),u=1;
for(int i=0;i<n;i++)
{
char c=s[i]-'a';
if(!ch[u][c]) ch[u][c]=++tot;
u=ch[u][c];
}
id[i]=u;
}
void build()
{
for(int i=0;i<26;i++) ch[0][i]=1;
queue<int> q;q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
Tf[fail[u]].push_back(u);
for(int i=0;i<26;i++)
if(!ch[u][i]) ch[u][i]=ch[fail[u]][i];
else fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
}
}
int st[N],ed[N];
void dfs(int u)
{
st[u]=++dn;
for(int v:Tf[u]) dfs(v);
ed[u]=dn;
}
void solve(int x,int u)
{
tr.upd(st[u],1);
for(int i:q[x]) ans[i]=tr.qsum(ed[id[i]])-tr.qsum(st[id[i]]-1);
for(int v:G[x]) solve(v,ch[u][c[v]-'a']);
tr.upd(st[u],-1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int op,j=0;
cin>>op;if(op==2) cin>>j;cin>>c[i];
G[j].push_back(i);
}
cin>>m;
for(int i=1;i<=m;i++)
{
int x;cin>>x>>s;
insert(i);q[x].push_back(i);
}
build();dfs(0);solve(0,1);
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}
CF1437G Death DBMS
又是一道失配树板题。
根据上面失配树的性质，相当于单点修，维护一条树链上的 max 值。树剖即可。
注意到可能有重复串，故用一个 multiset 维护某个结点的 max。
一些细节：失配树以 0 为根，重儿子初始为 -1，同时注意叶子结点不要遍历重儿子导致数组越界。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,tot=1,a[N];
int id[N],ch[N][26],fail[N];
int dn,sz[N],fa[N],son[N],top[N],dfn[N],rev[N];
char s[N];
vector<int> G[N];
multiset<int> S[N];
struct SegTree{
int mx[N*4];
#define lc (k<<1)
#define rc (k<<1|1)
#define mid (l+r>>1)
void build(int k=1,int l=1,int r=dn)
{
mx[k]=-1;
if(l==r) {mx[k]=S[rev[l]].size()?*S[rev[l]].rbegin():-1;return;}
build(lc,l,mid),build(rc,mid+1,r);
mx[k]=max(mx[lc],mx[rc]);
}
void upd(int x,int k=1,int l=1,int r=dn)
{
if(l==r) {mx[k]=S[rev[l]].size()?*S[rev[l]].rbegin():-1;return;}
x<=mid?upd(x,lc,l,mid):upd(x,rc,mid+1,r);
mx[k]=max(mx[lc],mx[rc]);
}
int qmx(int x,int y,int k=1,int l=1,int r=dn)
{
if(l>=x&&r<=y) return mx[k];
int res=-1;
if(x<=mid) res=qmx(x,y,lc,l,mid);
if(mid<y) res=max(res,qmx(x,y,rc,mid+1,r));
return res;
}
}tr;
void build()
{
for(int i=0;i<26;i++) ch[0][i]=1;
queue<int> q;q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
G[fail[u]].push_back(u);
for(int i=0;i<26;i++)
if(!ch[u][i]) ch[u][i]=ch[fail[u]][i];
else fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
}
}
void dfs1(int u)
{
sz[u]=1;son[u]=-1;
for(int v:G[u])
{
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf)
{
dfn[u]=++dn,rev[dn]=u,top[u]=topf;
if(~son[u]) dfs2(son[u],topf);
for(int v:G[u]) if(v!=son[u]) dfs2(v,v);
}
int Qmx(int x)
{
int mx=-1;
while(top[x]) mx=max(mx,tr.qmx(dfn[top[x]],dfn[x])),x=fa[top[x]];
return max(mx,tr.qmx(1,dfn[x]));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s;
int u=1,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
if(!ch[u][c]) ch[u][c]=++tot;
u=ch[u][c];
}
id[i]=u;S[u].insert(0);
}
build();
dfs1(0),dfs2(0,0);tr.build();
while(m--)
{
int op,i,x;cin>>op;
if(op==1)
{
cin>>i>>x;
S[id[i]].erase(S[id[i]].find(a[i]));
S[id[i]].insert(a[i]=x);
tr.upd(dfn[id[i]]);
}
else
{
cin>>s;
int u=1,len=strlen(s),mx=-1;
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
u=ch[u][c];
mx=max(mx,Qmx(u));
}
cout<<mx<<'\n';
}
}
}
P3167 通配符匹配
dp + hash 是最简单的。
注意到通配符数量很小。
定义 \(f_{i,j}\) 表示原串匹配到第 \(i\) 个通配符，文件串匹配到第 \(j\) 个字符是否可行。
假设第 \(i\) 个通配符在原串中位置为 \(p_i\)。
如果 s[p[i]]='*'，且 \(f_{i,j}=1\)，那么 \(\forall k>j,f_{i,k}=1\)。
设 \(l=p_i+1,r=p_{i+1}-1\)，如果 s[l,r]=t[j+1,j+1+r-l+1]，那么可以转移到 \(f_{i+1,j+1+r-l+1+1}\)。
这个可以用哈希来判断。
由于 ? 不能匹配空字符，我们钦定它必须要匹配一个才可行，即如果 s[p[i+1]]='?'，转移到的下标还要加一。
当然，为方便，我们保证原串结尾为通配符，就可以直接输出答案。
所以原串后面加一个 ?，文件串后面加任意一个字符（让这个问号匹配这个字符）。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
int n,m,q,k,pos[15],f[15][N];
ull pw[N],hs[N],ht[N];
char s[N],t[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);s[++n]='?';
pw[0]=1;for(int i=1;i<=1e5;i++) pw[i]=pw[i-1]*117;
for(int i=1;i<=n;i++)
{
hs[i]=hs[i-1]*117+s[i];
if(s[i]=='?'||s[i]=='*') pos[++k]=i;
}
cin>>q;
while(q--)
{
scanf("%s",t+1);
m=strlen(t+1);t[++m]='a';
for(int i=1;i<=m;i++) ht[i]=ht[i-1]*117+t[i];
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=0;i<=k;i++)
{
if(s[pos[i]]=='*') for(int j=1;j<=m;j++) f[i][j]|=f[i][j-1];
for(int j=0;j<=m;j++)
{
if(!f[i][j]) continue;
int ls=pos[i]+1,rs=pos[i+1]-1;
int lt=j+1,rt=lt+rs-ls;
if(hs[rs]-hs[ls-1]*pw[rs-ls+1]==ht[rt]-ht[lt-1]*pw[rt-lt+1]) f[i+1][rt+(s[pos[i+1]]=='?')]=1;
}
}
f[k][m]?puts("YES"):puts("NO");
}
}
P2336 喵星球上的点名
人类智慧 + hash 是最简单的，跑得也很快。
智慧结论：字符长度 \(\leq O(\sqrt{ \sum len})\) 种。
考虑 \(1 \sim n\) 的字符长度全部出现一遍，那么总长度为 \(\sum\limits_{1\leq i\leq n} i \approx n^2\)。
对于所有模式串，哈希一下，然后用哈希表存一下出现次数。
那么对于一个字符串 \(S\)，对于当前位置 \(i\)，截取所有在模式串中出现过的长度为 \(l\) 的字符串，然后哈希判断是否在模式串中出现。
复杂度 \(O(n\sqrt{\sum len})\)，非常巧妙。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e5+5,base=10007;
int n,m,ans[N];
ull pw[N],hs[N],ht[N];
vector<int> v,s[N];
unordered_map<ull,int> cnt,vis,res;
char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
int x=0,f=1;char c=nc();
for(;!isdigit(c);c=nc()) if(c=='-') f=-1;
for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
{
int l=rd();
while(l--) s[i].push_back(rd()+1);
s[i].push_back(10002);//中间加个不存在的字符，拼成一个串。
l=rd();
while(l--) s[i].push_back(rd()+1);
}
pw[0]=1;for(int i=1;i<=1e5;i++) pw[i]=pw[i-1]*base;
for(int i=1;i<=m;i++)
{
int l=rd();ull t=0;
v.push_back(l);
while(l--) t=t*base+rd()+1;
ht[i]=t,cnt[t]++;
}
sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++)
{
vis.clear();
hs[0]=s[i][0];
for(int j=1;j<s[i].size();j++) hs[j]=hs[j-1]*base+s[i][j];
for(int j=0;j<s[i].size();j++)
for(int len:v)
{
int l=j-len+1,r=j;
if(l<0) break;
ull t=hs[r]-(l-1<0?0:hs[l-1])*pw[len];
if(cnt.count(t)&&!vis.count(t)) ans[i]+=cnt[t],vis[t]=1,res[t]++;
}
}
for(int i=1;i<=m;i++) cout<<res[ht[i]]<<'\n';
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}