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]<<' ';
}

本栏目推荐文章
• C++实现文件内查找字符串
• python字符串方法
• 字符串格式化
• SQL SERVER日期时间转字符串
• 字符串的拼接
• 每日一题 2024-1-13 构造限制重复的字符串
• 正则表达式复习二——元字符
• 采用递归的方法简化函数 在允许创建临时变量的前提下实现求字符串长度
• 【Python】【OpenCV】OCR识别（三）——字符识别
• 数论专题

字符串 字符 专题 cw字符串 字符 专题cw 字符串 指针 字符 专题 字符串 字符 专题 字符串 字符 专题01 字符串 字符 专题cwoi 模拟赛 字符串 字符 专题 字符 编码unicode专题 字符串 几何 字符 专题 字符 专题ctfer misc 字符串 字符 基础 专题