匹配 hash

lkjzyd20 · 2025-03-31 15:50:08 · 算法·理论

Tags: 字符串 hash

匹配 hash

https://www.cnblogs.com/henry-1202/p/10324966.html

LOJ 字串查找

一道入门题。

给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数。A 和 B 中的字符均为英语大写字母或小写字母，A 中不同位置出现的 B 可重叠。

字符串哈希模板题。

思路

https://www.luogu.com.cn/article/2cuvkgn0

基于哈希的思想，我们可以将一个字符串通过哈希函数转换成为 x 进制的数值。

可是，我们该如何获取字符串在区间 [L,R] 内的哈希值呢？这里有一个例子：

在字符串 s=\text{9723761} 中，我们想截取区间 [3,6] 的哈希值，也就是 \text{2376} 的哈希值。我们或许可以尝试类似于前缀和的思路：hs_i 表示前 i 个字符串的哈希值。那么，\text{2376} 的哈希值就可以被表示为 \text{972376} 的哈希值 hs_R 减去 \text{970000} 的哈希值 hs_{L-1}\times10^{R-L+1}，即 hs_R-hs_{L-1}\times10^{R-L+1}。

然而，实际上我们会将字符串转换为 base 进制的数值，所以答案应为 hs_R-hs_{L-1}\times base^{R-L+1}，我们可以预处理 pw_i=base^i，pw 可以递推得到，pw_0=1。这样就保证了我们可以以 \mathcal{O}(1) 的时间复杂度获取区间内的哈希值了。最后检查 [l1,r1] 和 [l2,r2] 的哈希值是否相同即可。

注意，我这里使用的是单哈希，如果 base 不选好，可能会导致哈希冲突！

为什么会有哈希冲突？

我们的答案会呈现出 hs_R-hs_{L-1}\times base^{R-L+1} 的形式，但是，我们的数据范围是保存不下这样的数的，所以我们一般使用 \text{unsigned long long} 来自然溢出，在 C++ 语言中，\text{unsigned long long} 类型是一种整型，用来存储非常大的非负整数，相当于每一次计算时的答案如果大于 2^{64}-1 就会自动取模。

但是，我们会发现，有可能有多个数对 2^{64}-1 取模的结果是相同的，这就是为什么会有哈希冲突。

当然，你也可以不使用 \text{unsigned long long}，直接使用一个较大的质数取模，原理是一样的，难写一点罢了。

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=1e6+10,base=233331;
char s1[N],s2[N];
int n1,n2;
unsigned long long f1[N],f2[N],G[N];
void init(){
    G[0]=1;
    rep(i,1,n1)G[i]=G[i-1]*base;
    rep(i,1,n1)f1[i]=f1[i-1]*base+s1[i];
    rep(i,1,n2)f2[i]=f2[i-1]*base+s2[i];
}
unsigned long long calc(int l,int r){
    return f1[r]-f1[l-1]*G[r-l+1];
}
main(){
    cin>>(s1+1)>>(s2+1);
    n1=strlen(s1+1);n2=strlen(s2+1);
    init();
    int tot=0;
    rep(i,1,n1-n2+1)if(calc(i,i+n2-1)==f2[n2])++tot;
    cout<<tot;
    return 0;
}

「一本通 2.1 练习 1」Power Strings

询问每个字符串最多是由多少个相同的子字符串重复连接而成的。

我们枚举字符串长度的约数，然后直接暴力哈希匹配判断即可。

这是后面一个题的弱化版，待会会讲解加强版。

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=2e6+10,base=233331;
unsigned long long f[N],G[N];
char s[N];
int n;
void init(){
    G[0]=1;
    rep(i,1,N-10)G[i]=G[i-1]*base;
}
unsigned long long calc(int l,int r){return f[r]-f[l-1]*G[r-l+1];}
void solve()
{
    n=strlen(s+1);
    rep(i,1,n)f[i]=f[i-1]*base+s[i];
    for(int i=1;i<=n;++i){
        if(n%i==0){
            unsigned long long x=calc(1,i);
            for(int j=1;j<=n;j+=i)if(calc(j,j+i-1)!=x)goto aa;
            cout<<n/i<<'\n'; return;
            aa:;
        }
    }
    cout<<"1\n";return;
}
main(){
    init();
    for(;;)
    {
        cin>>(s+1);
        if(s[1]=='.')exit(0);
        solve();
    }
    return 0;
}

「一本通 2.1 练习 2」Seek the Name, Seek the Fame

这个题是下个题的必要条件，所以还是讲一下吧。

题意：对于每个字符串中求出所有既是前缀又是后缀的子串长度。

我们对于每一个前缀求出它的哈希值 [1,i]，对于每一个后缀求出它的哈希值 [n-i+1,n]。

```cpp #include <bits/stdc++.h> //#define int long long #define rep(i, l, r) for(int i = l; i <= r; ++ i) #define per(i, r, l) for(int i = r; i >= l; -- i) using namespace std; const int N=2e6+10,base=233331; unsigned long long f[N],G[N]; char s[N]; int n; void init(){ G[0]=1; rep(i,1,N-10)G[i]=G[i-1]*base; } unsigned long long calc(int l,int r){return f[r]-f[l-1]*G[r-l+1];} void solve() { n=strlen(s+1); rep(i,1,n)f[i]=f[i-1]*base+s[i]; for(int i=1;i<=n;++i) if(calc(1,i)==calc(n-i+1,n))cout<<i<<' '; cout<<'\n'; } main(){ init(); for(;cin>>(s+1);) solve(); return 0; } ``` ### CF126B Password Z 函数模板题，但是这里使用哈希解法。简要题意：找到一个字符串同时是 $S$ 的前缀、后缀、非前后缀子串。如样例：fixprefixsuffix，输出 fix 思路：我们先找出所有合法的可以一一对应的前后缀 $T$，把它们的下标存起来。思考可以发现，如果有一个存在一个非前后缀子串 $U$，那么一个比 $T$ 短的前缀也一定能找到对应的 $U'$，这个很明显具有单调性，二分即可。 ```cpp #include <bits/stdc++.h> #define int long long #define rep(i, l, r) for(int i = l; i <= r; ++ i) #define per(i, r, l) for(int i = r; i >= l; -- i) using namespace std; const int N=1000010,base=233331,p=1e9+7; int G[N],f[N]; char s[N]; int n; void init() { G[0]=1; rep(i,1,n){ G[i]=G[i-1]*base%p; f[i]=(f[i-1]*base%p+s[i]-'0')%p; } } int calc(int l,int r){return (f[r]-f[l-1]*G[r-l+1]%p+p)%p;} vector<int>v; bool check(int x) { int val=calc(1,x); rep(i,2,n-x) if(val==calc(i,i+x-1))return 1; return 0; } main() { cin>>(s+1); n=strlen(s+1); init(); rep(i,1,n) if(calc(1,i)==calc(n-i+1,n))v.push_back(i); int l=0,r=(int)v.size()-1,ans=-1; for(;l<=r;) { int mid=(l+r)>>1; if(check(v[mid]))l=mid+1,ans=v[mid]; else r=mid-1; } if(ans==-1)puts("Just a legend"),exit(0); rep(i,1,ans)putchar(s[i]); return 0; } ``` #### P6739 [BalticOI 2014] Three Friends (Day1) 有一个字符串 $S$，对他进行操作： 1. 将 $S$ 复制为两份，存在字符串 $T$ 中 2. 在 $T$ 的某一位置上插入一个字符，得到字符串 $U

现在给定 U，求 S。

我们将问题转化：

现在有一个字符串 S，每次询问它的一个子串删除其中一个字符后的哈希值。

假设我们现在询问的区间为 [l,r]，删除的字符位置为 x，类比上面的做法，我们可以先 O(1) 得到区间 [l,x−1] 和区间 [x+1,r] 的哈希值，那么现在要做的事情就是把这两段拼起来了，其实很简单，强行将前面的区间强行左移 r−(x+1)+1 位。

接着再来思考这道题，由于 U 串是 S 串复制两次后插入一个字符所得，因此长度必然为奇数。

接下来，将得到的字符串分成左右两部分，并分别记录这两段的哈希值。然后枚举删中的字符，若所得字符串与后半段相等就统计答案，最后分类讨论即可。

#include <bits/stdc++.h>
#define int unsigned long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=2e6+10;
int n,mid,ans_id,tot;
string s;
const int base=133331,p=1e9+7;
int G[N],f[N];
unordered_map<int,bool>vis;
void init()
{
    G[0]=1;
    rep(i,1,n){
        G[i]=G[i-1]*base;
        f[i]=f[i-1]*base+s[i];
    }
}
int calc(int l,int r){return f[r]-f[l-1]*G[r-l+1];}
int del_calc(int l,int x,int r){
    return calc(l,x-1)*G[r-x]+calc(x+1,r);
}
bool check(int x)
{
    int l=0,r=0;
    if(x==mid)
    {
        l=calc(1,x-1);
        r=calc(x+1,n);
    }
    if(x<mid)
    {
        l=del_calc(1,x,mid);
        r=calc(mid+1,n);
    }
    if(x>mid)
    {
        l=calc(1,mid-1);
        r=del_calc(mid,x,n);
    }
    if(l==r&&!vis[l]){vis[l]=1;return 1;}
    return 0;
}
main()
{
    cin>>n>>s;
    s="0"+s;
    if(!(n&1))puts("NOT POSSIBLE"),exit(0);
    mid=(n+1)>>1;
    init();
    rep(i,1,n)
        if(check(i))
        {
            ans_id=i;
            tot++;
        }
    if(tot>1)puts("NOT UNIQUE"),exit(0);
    if(!tot)puts("NOT POSSIBLE"),exit(0);
    if(ans_id==mid)rep(i,1,mid-1)cout<<s[i];
    else if(ans_id<mid) rep(i,mid+1,n)cout<<s[i];
    else rep(i,1,mid-1)cout<<s[i];
    return 0;
}

「POI2010」珍珠项链 Beads

给出 n 个数，可将它们分为若干个串，每个串有 k 个数（长度不足 k 则丢弃），求使得不同的串最多的 k 值及串的个数。串可翻转，即子串 1,2,3 和 3,2,1 被认为是一样的。

首先，因为串可以被反转，所以我们要保存这个序列的倒序哈希。

代码长这样：

void init(){
    g[0]=1;
    rep(i,1,n)g[i]=g[i-1]*base;
    per(i,n,1)f[i]=f[i+1]*base+a[i];
}
int calc(int l,int r){return f[l]-f[r+1]*g[r-l+1];}

接下来思考时间复杂度，枚举 k 要O(n)的时间复杂度，而串有 \lfloor\dfrac{n}{k}\rfloor 个，所以枚举的时间复杂度为

\displaystyle\sum_{k=1}^n\lfloor\dfrac{n}{k}\rfloor

这个可以看似近似 O(n \log_2 n) 的时间复杂度。

我们按照题面模拟就可以了，对于每一次判断，我们用 map 保存哈希值，然后判重即可，但是会发现会 TLE 一个点，考虑优化，对于每个 i，最多能分割出 \lfloor\dfrac{n}{i}\rfloor 个子串。若 \lfloor\dfrac{n}{i}\rfloor < tot，即使所有子串都不同，也无法更新答案，故无需继续检查更大的 i。

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=2e5+10,base=233331;
int n;
int a[N];
unsigned long long f1[N],f2[N],g[N];
int calc1(int l,int r){return f1[r]-f1[l-1]*g[r-l+1];}
int calc2(int l,int r){return f2[l]-f2[r+1]*g[r-l+1];}
void init(){
    g[0]=1;
    rep(i,1,n)g[i]=g[i-1]*base;
    rep(i,1,n)f1[i]=f1[i-1]*base+a[i];
    per(i,n,1)f2[i]=f2[i+1]*base+a[i];
}
int ans[N],cnt,tot;
unordered_map<int,bool>mp;
main()
{
    cin>>n;
    rep(i,1,n)cin>>a[i];
    init();
    rep(i,1,n){
        if(n/i<tot)break;
        int sum=0;
        for(int j=1;j<=n;j+=i){
            if(j+i-1>n)break;
            int xx=calc1(j,j+i-1);
            int yy=calc2(j,j+i-1);
            if(!mp[xx]&&!mp[yy]){
                mp[xx]=mp[yy]=1;
                ++sum;
            }
        }
        if(sum>tot){
            tot=sum;
            cnt=1;
            ans[1]=i;
        }
        else if(sum==tot)ans[++cnt]=i;
        mp.clear();
    }
    cout<<tot<<' '<<cnt<<'\n';
    rep(i,1,cnt)cout<<ans[i]<<' ';
    return 0;
}

「POI2010」反对称 Antisymmetry

Manacher 模板题，不知道 pyf 会讲不。。。

这里提供一种哈希解法。

我们先求出异或后的倒序哈希，我们枚举每个回文串的中间轴，对于每一个 i，我们用二分去延申左右端点，判断是否合法，为什么可以二分呢，因为如果一个串 s 为反对称字符串，那么 s 所有以 l 为中轴的子串都是反对称字符串，这样的子串共有 l\div 2 个。

总结一下，Manacher 这种问题一般是求 S 中最长回文串的长度，但是我们可以使用哈希加二分来进行求解，这种思路对于考场是十分管用的，它实现简单，清晰易懂，就是时间复杂度慢了点。

考场上也有这种题，比如单调队列优化 dp 可以使用线段树写，这个时候就要仔细思考代码时空复杂度，代码长度和代码简易难度之间的关系。

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=5e5+10,base=233331;
int n;
unsigned long long f1[N],f2[N],g[N];
char s1[N],s2[N];
int calc1(int l,int r){return f1[r]-f1[l-1]*g[r-l+1];}
int calc2(int l,int r){return f2[l]-f2[r+1]*g[r-l+1];}
void init(){
    g[0]=1;
    rep(i,1,n)g[i]=g[i-1]*base;
    rep(i,1,n)f1[i]=f1[i-1]*base+s1[i];
    per(i,n,1)f2[i]=f2[i+1]*base+s2[i];
}
long long sum;
bool check(int x,int y){
    return calc1(x,y)==calc2(x,y);
}
int solve(int x){
    int l=0,r=min(n-x,x),ans=0;
    for(;l<=r;){
        int mid=(l+r)>>1;
        if(check(x-mid+1,x+mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
main()
{
    cin>>n;
    cin>>(s1+1);
    rep(i,1,n)s2[i]='0'+(s1[i]!='1');
    init();
    rep(i,1,n)
        sum+=solve(i);
    cout<<sum;
    return 0;
}

[POI 2012] OKR-A Horrible Poem

一道深刻利用了字符串性质的题。

询问每个字符串的某个子串最多是由多少个相同的子字符串重复连接而成的。

盗个图，有一个结论，如果 S_1 与 S_2 相等，那么 X_1 就为这个字符串的循环节。

我令下张图片上一行的字符串为截取的 S_1，下一行为截取的 S_2。

对于一个字符串，我们可以发现，如果 S_1 和 S_2 相等，那么 X_1 和 X_2 就会相等，又因为 X_2 是从 X_3 中截取的，所以 X_2 和 X_3 就会相等。由此往后推，可以发现结论显然。

另外循环节的长度的循环次数都一定是总长的约数，我们可以先预处理出每一个数的约数，存到 \text{vector} 里，暴力查询即可。

我们可以这样：

vector<int>v[N];
void prime(){
    rep(i,1,n)
        for(int j=i;j<=n;j+=i)v[j].push_back(i);
}

这么做就可以拿下 LOJ 的满分（评测鸡这么快）了，但是 luogu 和 bzoj 是过不了的。

我们使用 \text{SPF} 筛法，它的核心思想是预处理出 1 到 n 内每个数的最小质因数，然后快速进行质因数分解，进而生成所有约数。

i	1	2	3	4	5	6	7	8	9	10
\text{SPF}_i	1	2	3	2	5	2	7	2	3	2

有了 \text{SPF} 数组后，可以使用贪心法快速进行质因数分解。例如，对于 x = 18：

最终，我们得到了 18 的质因数分解：2^1 \times 3^2。

使用筛法构造最小质因数数组，步骤如下：

初始化默认每个数都是质数。
遍历 2 到 \sqrt{n} 的所有整数：若 i 仍然是质数，则枚举 i 的倍数 j，并更新 spf_j =i（前提是 spf_j 仍未被更新）。
经过遍历，每个合数 j 都会记录其最小的质因数。

int spf[N];
void solve(int n) {
    for (int i = 1; i <= n; i++) spf[i] = i;
    for (int i = 2; i * i <= n; i++) {
        if (spf[i] == i) { 
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
    }
}

已知 x 的质因数分解结果（p^{e_1}_1\times p^{e_2}_2 \dots \times p^{e_k}_k），则可以通过递归方法生成所有可能的约数。

例如，18 的质因数分解为：2^1 \times 3^2，则约数为：

2^0\times 3^0=1\\ 2^0\times 3^1=3\\ 2^0\times 3^2=9\\ 2^1\times 3^0=2\\ 2^1\times 3^1=6\\ 2^1\times 3^2=18

对于每一次查询生成的约数，我们生成的约数在 2\times 10^6 内最多不到 200 个，相当于之前的遍历查询，而 \text{SPF} 筛法的时间复杂度是 O(n) 的，所以可以通过此题。

在代码实现方面，需要一些优化，例如求解哈希函数时使用 inline，读入和输出（不要使用递归输出，使用栈函数）优化

总结，这是一道巧妙运用字符串性质和数学的题目，这启发我们不断优化代码，不断思考算法的本质。

#include <bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
#define gc getchar
inline void read(int &n){
    char c=getchar();
    for(;c<48||c>57;c=getchar());
    for(n=0;c>47&&c<58;c=getchar())n=(n<<1)+(n<<3)+c-48;
}
inline void write(int x){
    if(x==0){putchar(48);return;}
    char s[11];int i=0;
    for(;x;x/=10)s[i++]=x%10+48;
    for(;i;)putchar(s[--i]);
}
const int N=2e6+10;
const unsigned int base=97;
unsigned int f[N],G[N];
char s[N];
int n,spf[N];
void init(){
    G[0]=1;
    rep(i,1,n)G[i]=G[i-1]*base;
    rep(i,1,n)f[i]=f[i-1]*base+s[i];
    rep(i,1,n)spf[i]=i;
    for(int i=2;i*i<=n;++i)
        if(spf[i]==i)
            for(int j=i*i;j<=n;j+=i)
                if(spf[j]==j)spf[j]=i;
}
inline unsigned int calc(int l,int r){return f[r]-f[l-1]*G[r-l+1];}
void dfs(vector<pair<int,int>> &s,vector<int> &V,int pos,int sum){
    if(pos==(int)s.size()){
        V.push_back(sum);
        return;
    }
    rep(i,0,s[pos].second){
        dfs(s,V,pos+1,sum);
        sum*=s[pos].first;
    }
}
vector<int>V[N];
vector<int> to_get(int x) {
    if(!V[x].empty())return V[x];
    vector<pair<int,int>> s;
    int tmp=x;
    for(;tmp>1;){
        int p=spf[tmp],cnt=0;
        for(;tmp%p==0;++cnt,tmp/=p);
        s.push_back({p,cnt});
    }
    dfs(s,V[x],0,1);
    sort(V[x].begin(),V[x].end());
    return V[x];
}
void solve(){
    int x,y;read(x);read(y);
    vector<int> v=to_get(y-x+1);
    for(int d:v) if(calc(x,y-d)==calc(x+d,y)){write(d),putchar('\n');return;}
}
int main(){
    read(n);
    rep(i,1,n)s[i]=getchar();
    init();
    int Q;read(Q);
    for(;Q;--Q)solve();
    return 0;
}

相信你一定也能 A 了这道模板题，加油！！！

替代难写的后缀排序。

我们可以转化问题：如何快速判断两个字符串大小？

首先，我们可以先用 O(|S|) 的时间复杂度来预处理出每个字符串的哈希值，然后就可以 O(1) 判断两个字符串是否相同。接着我们使用二分求出这两个字符串的最长公共前缀的位置 l_1,l_2，最后判断 S1_{l_1+1} 和 S2_{l_2+1} 的大小即可，时间复杂度为 O(\log |S|)。

把这个实现放在排序的 cmp 函数就可以了，时间复杂度为 O(n\log^2 n)。

注意事项：

二分的时候一定要确定好 [l,r] 区间的左右边界，这个是可以加速的。
使用稳定的 stable_sort，这个内部采用归并排序，当有额外内存可用时，复杂度为 O(n\log n)（luogu 竟然卡我），如果内存很少，采用常数较大原地排序算法。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
using namespace std;
const int N=1e6+10,base=233331;
int n;
char str[N];
int a[N];
unsigned int f[N],g[N];
void init(){
    g[0]=1;
    rep(i,1,n){
        f[i]=f[i-1]*base+str[i];
        g[i]=g[i-1]*base;
        a[i]=i;
    }
}
unsigned int calc(int l,int r){return f[r]-f[l-1]*g[r-l+1];}
bool cmp(int l1,int l2){
    int l=1,r=min(n-l1+1,n-l2+1);
    for(;l<=r;){
        int mid=(l+r)>>1;
        if(calc(l1,l1+mid-1)==calc(l2,l2+mid-1))l=mid+1;
        else r=mid-1;
    }
    return str[l1+l-1]<str[l2+l-1];
}
main()
{
    cin>>(str+1);n=strlen(str+1);
    init();
    stable_sort(a+1,a+n+1,cmp);
    rep(i,1,n)cout<<a[i]<<' ';
    return 0;
}