听课笔记 - 2026 上海 - 15 字符串【哈希】【Manacher】【KMP】【Trie】【ACAM】

ExFish · 2026-08-20 08:22:52 · 算法·理论

字符串哈希 & Trie

字符串哈希就是直接将字符串转为数值，对其取模映射。一般是很难冲突的。Trie 适合多个文本串的匹配问题（完全一致，而不是 ACAM 的多个存在问题的 Fail 指针），但是空间需求较大。

Manacher

线性求回文串。首先回文串有奇长度也有偶数长度，回文中心可能不存在。所以左右两边加 < 和 >，中间加 # 就可以使得最长回文串所有端点在字母上，且都可以转为奇长度回文串（直接 \lfloor \frac{x}{2} \rfloor 就可以得到原始长度）。

首先我们求最长回文串显然要的东西就是 p_i：一个位置的最长延申长度。我们设当前回文最大右端点为 r=k+p_k，那么此时情况就是回文串从 k 出发且长为 p_k，右端点最大。那么如果此时我们要更新 j，j\ge r 就说明 j 这个扩张中心没被覆盖，此时只能暴力扩展，而不会被更新（这说明了其在前面压根就没被用过）。

否则，j 就被一个回文串包含，此时我们的 p 可以快捷更新了 p_j=\min(p_{2k-j},p_{k}+k-j)。你可能好奇这为什么是对的。首先，你考虑此时对于 k，有 k\to j 和 j'\leftarrow k 两个字符串，它们是对称的。这个 j' 就等于 2k-j。然后我们把眼光放在 [p_k-k,p_k+k] 之间，此时在这个区间内，p_{2k-j}=p_{j'} 一定可以转移到 p_j。这是为什么呢？若这个对称点没有超过完整的范围，则此时就会发现 p_{j'} 在 p_k 之中，是一个回文中的回文。由于回文左右镜像，所以右侧 j 的位置肯定会出现一个一模一样的字符串。此时就有 p_{2k-j}\to p_j。但是问题来了，万一超出了 p_k+k 呢？那么我们就需要限制这个回文的长度。你会发现，p_{j'} 的左边可以截掉出去的部分，这样一定符合 j 的情况。那么我们在 j 可以截掉右边出去的部分，这个部分长度就是 p_k+k-j 也就是 j 到右端点的距离。得到刚刚那个转移式子。

for(int j=1;j<n;j++){
    if(j<r) p[j]=min(p[2*k-j],p[k]+k-j);
    else p[j]=1;
    while(s[j+p[j]]==s[j-p[j]]) ++p[j];
    if(p[j]+j>r) k=j, r=p[k]+k;
} 

复杂度分析：一个点最多被一个回文串超出扩张范围地扩张到，所以复杂度为 \mathcal O(n)。

【完成】P3538 [POI 2012] OKR-A Horrible Poem

字符串哈希。如果一个区间头尾都去掉一节还是相等的，那么说明就有每一节都等于前一节。稍微想想就可以知道这样能判循环节。然后循环节一定是因数个。一个数不行必定要除以其最小质因数，查询是 \log 的。

很多细节，看看代码。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=5e5+10;
const int B=131;
int n; string s;
int q;
int mn[N];
ull h[N],pw[N];
inline ull gethash(int l,int r){ return h[r]-h[l-1]*pw[r-l+1]; }
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s; s=" "+s;
    pw[0]=1,h[0]=1;
    for(int i=1;i<=n;i++)
        h[i]=h[i-1]*B+(s[i]-'a'+1),
        pw[i]=pw[i-1]*B;
    for(int i=2;i<=n;i++)if(!mn[i]){
        mn[i]=i;
        for(int j=i;j<=n;j+=i) if(!mn[j]) mn[j]=i;
    }
    cin>>q;
    while(q--){
        int l,r; cin>>l>>r;
        int len=r-l+1, ans=len, now=len; // ans 记录的是目前最小合法重复长度，now 记录的是所有可能的分段长度
        while(1){
            if(now==1) break; 
            int nxt=ans/mn[now]; // nxt 记录的是目前枚举到的合法长度（使用 now 的最小因数去除以保证合法性）
            if(gethash(l+nxt,r)==gethash(l,r-nxt)) ans=nxt;
            now=now/mn[now]; // 获取新的长度
        }
        cout<<ans<<"\n";
    }
    return 0;
}

ABC284F ABCBAC

找一组串，使得删除一段区间后剩下的字符串正常拼接等于删除的字符串反转过来。直接字符串哈希就过了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N=2e6+10;
const ll P=1e9+9;
const ll B=131;
int n; string t;
ull hs[N],pw[N],h2[N];
ll hs2[N],pw2[N],h22[N];
ull gethash(int l,int r){ return (l>r)?0ull:hs[r]-hs[l-1]*pw[r-l+1]; }
ull gethsh2(int l,int r){ return (l>r)?0ull:h2[r]-h2[l-1]*pw[r-l+1]; }
ll gethash2(int l,int r){ return (l>r)?0ll:(hs2[r]-hs2[l-1]*pw2[r-l+1]%P+P)%P; }
ll gethsh22(int l,int r){ return (l>r)?0ll:(h22[r]-h22[l-1]*pw2[r-l+1]%P+P)%P; }
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t; t=" "+t;
    pw[0]=pw2[0]=1;
    for(int i=1;i<=(n<<1);i++) pw[i]=pw[i-1]*B;
    for(int i=1;i<=(n<<1);i++) hs[i]=hs[i-1]*B+(t[i]-'a'+1);
    for(int i=1;i<=(n<<1);i++) h2[i]=h2[i-1]*B+(t[(n<<1)-i+1]-'a'+1);
    for(int i=1;i<=(n<<1);i++) pw2[i]=pw2[i-1]*B%P;
    for(int i=1;i<=(n<<1);i++) hs2[i]=(hs2[i-1]*B%P+(t[i]-'a'+1))%P;
    for(int i=1;i<=(n<<1);i++) h22[i]=(h22[i-1]*B%P+(t[(n<<1)-i+1]-'a'+1))%P;
    for(int i=0;i<=n;i++){
        ull le=gethash(1,i), ri=gethash(i+n+1,n+n), mi=gethsh2(n-i+1,n+n-i);
        ll l2=gethash2(1,i), r2=gethash2(i+n+1,n+n), m2=gethsh22(n-i+1,n+n-i);
        if(le*pw[n-i]+ri==mi&&(l2*pw2[n-i]%P+r2)%P==m2%P){
            for(int j=n-i+1;j<=n+n-i;j++) cout<<t[n+n-j+1]; 
            cout<<"\n"<<i;
            return 0;
        }
    }
    cout<<"-1";
    return 0;   
}

【完成】[ABC135F] Strings of Eternity

你发现因为问的是子串，首先我们可以使得 |S|>2|T|。所以本质上 s 就是一个环，那么就是在 s+s 这个字符串上找到最长连续 t 的个数。至于判无限解答案，就是对于一个串能分配到超过一个答案，具体看代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
const ll P=1e9+9;
const int N=5e5+10, tN=2e7+10;
const int B=131;
ll pw[tN], hs[tN], ths;
int n,m,pre[tN],ans;
string s,t;
ll gethash(int l,int r){
    if(l>r) return -1;
    return (hs[r]-hs[l-1]*pw[r-l+1]%P+P)%P;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>t;
    while(t.size()*2>s.size()) s=s+s;
    s=s+s;
    n=s.size(), m=t.size();
    s=" "+s;
    t=" "+t;
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*B%P;
    for(int i=1;i<=n;i++) hs[i]=(hs[i-1]*B%P+(s[i]-'a'+1))%P;
    for(int i=1;i<=m;i++) ths=(ths*B%P+(t[i]-'a'+1))%P;
    for(int i=1;i+m-1<=n;i++)
        if(ths==gethash(i,i+m-1)) pre[i]=1;
    for(int i=n-m+1;i>=1;i--) // 注意长度要间隔 m 个
        if(pre[i]) pre[i]+=pre[i+m], ans=max(ans,pre[i]);
    if(ans+1>=n/m) cout<<-1;
    else cout<<ans;
    return 0;
}

【完成】P3426 [POI 2005] SZA-Template

印章覆盖整段。首先你发现第一次和最后一次贴左右边界，所以印章必须是 Border 之一。然后就可以利用 Border 的性质进行 DP。总时间复杂度为 \mathcal O(n)。

https://www.luogu.com.cn/article/yzql9zhi

【完成】P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands

前后缀拼一起然后跑 ACAM。

#include<bits/stdc++.h>
using namespace std;
// #define debug
int mp[500];
int n,m;
namespace ACAM{
    const int N=3e6+10, M=6;
    int tot, nxt[N][M], fail[N], root=0, ans[N], mrk[N], ind[N];
    vector<int> endon[N];
    void insertString(string s,int sid){
        #ifdef debug
            cout<<"Inser String : "<<s<<" , id = "<<sid<<"\n";        
        #endif
        int p=root;
        for(auto v:s){
            if(!nxt[p][mp[v]]) nxt[p][mp[v]]=++tot;
            p=nxt[p][mp[v]];
        }
        endon[p].push_back(sid);
    }
    void buildFail(){
        queue<int> q;
        for(int i=0;i<6;i++)
            if(nxt[root][i]) q.push(nxt[root][i]), fail[i]=root;
        while(q.size()){
            int p=q.front(); q.pop();
            for(int i=0;i<6;i++){
                int v=nxt[p][i];
                if(!v) nxt[p][i]=nxt[fail[p]][i]; // miss on p->v by i
                else fail[v]=nxt[fail[p]][i], ind[fail[v]]++, q.push(v);
            }
        }
        return;
    }
    void query(string s){
        #ifdef debug
            cout<<"Query String : "<<s<<"\n";        
        #endif
        int p=root;
        for(auto v:s){
            mrk[p]++;
            p=nxt[p][mp[v]];
        }
        return;
    }
    void topoCount(){
        queue<int>q;
        for(int i=1;i<=tot;i++)
            if(!ind[i]) q.push(i);
        while(q.size()){
            int p=q.front(); q.pop();
            mrk[fail[p]]+=mrk[p];
            for(auto v:endon[p]) ans[v]=mrk[p];
            ind[fail[p]]--;
            if(!ind[fail[p]]) q .push(fail[p]); 
        }
        return;
    }
}
using namespace ACAM;
int main(){   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    mp['A']=0, mp['G']=1, mp['U']=2, mp['C']=3, mp['#']=4, mp['&']=5;
    cin>>n>>m;
    string T=""; 
    for(int i=1;i<=n;i++){ string s; cin>>s; s=s+"#"+s+"&"; T+=s;  }
    for(int i=1;i<=m;i++){ string p,q; cin>>p>>q; insertString(q+"#"+p,i); }
    buildFail();
    query(T);
    topoCount();
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

P9482 [NOI2023] 字符串

给你 i,r 问 l\in [1,r] 有多少个满足 s[i,i+l-1]<rev(s[i+l,i+2l-1])。我们考虑更换定义，为一个区间长度为 2l 合法为题意中的条件，那么此时我们设 f(i,l) 为是否为合法串，转移是简单的，但是是 n^2 的，我们考虑使用 Bitset 优化。转移式如下：

• 否则 s_i<s_{i+2j-1} 显然是合法的，f_{i,j}=1。
• 之后就会有一组相等 s_i=s_{i+2j-1}，缩小范围即可得到答案，f_{i,j}=f_{i+1,j-1}。

先扔个 Bitset 上来。

const int tN=(1e5/64)+10;
const int w=6, p=63;
struct Bitset{
    #define ull unsigned long long
    #define pc __builtin_popcountll
    #define rep(i,n) for(int (i)=0;(i)<(n);++(i))
    ull a[tN];
    inline void reset(){ memset(a,0,sizeof(a)); }        // 清空 Bitset 
    inline void set(int x){ a[x>>w]|=1ull<<(x&p); }      // 设置一位为 1 
    inline void flip(int x){ a[x>>w]^=1ull<<(x&p); }     // 翻转一位数值
    inline int get(int x){ return (a[x>>w]>>(x&p))&1; }  // 获取某位的具体值 
    inline void operator|=(const Bitset &f){ rep(i,N) a[i]|=f.a[i]; } // Bitset |=
    inline void operator^=(const Bitset &f){ rep(i,N) a[i]^=f.a[i]; } // Bitset ^=
    inline void operator&=(const Bitset &f){ rep(i,N) a[i]&=f.a[i]; } // Bitset &= 
    inline int count(int x=N-1){ int r=pc(a[x>>w]&((1ull<<(x&p))-1)); rep(i,x>>w){ r+=pc(a[i]); } return r; } // 查询一个前缀的 1 个数 
    inline void leftmove(){ ull pre=0; rep(i,N){ int mx=(a[i]>>p)&1; a[i]=a[i]<<1|pre; pre=mx; } } // Bitset 整体左移一位 
};