题解：P11705 「KTSC 2020 R1」字符串查找

maxiaomeng · 2026-03-06 20:30:10 · 题解

题意

题意明确，不再赘述。

做法

匹配规则相当于无视字符具体是啥，只考虑字符间相等关系后是否相等。

定义某字符串的 h 数组 h_{i,j} 表示该字符串的第 j 个字符是否为 i，是则为 1，否则为 0。

此时不难发现：两个字符串匹配当且仅当两个字符串的 h 数组每行任意排列后相等。

如何判断？众所周知，两个数组任意排列后相等当且仅当它们排序后相等。

同样的，给 h 数组每行求个哈希，得到一个 26 个哈希值组成的哈希值数组，并将该数组升序排序。此时直接比较哈希值数组。即可判断是否匹配。

于是直接预处理 P 的哈希值数组。枚举 T 中每个长度为 M 的子串的哈希值数组与 P 的哈希值数组比较即可。

:::success[code]

#include<bits/stdc++.h>
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
#define endl '\n'
using namespace std;
const int N=1000005,base1=1511,mod1=15112511,base2=863,mod2=25111511;
char s[N],t[N];
int n,m;
vector<pr>h[N];
signed findP(char T[], char P[], signed N, signed M){
    n=N,m=M;
    strcpy(s+1,T);
    strcpy(t+1,P);
    for(int i=1;i<=n;i++)s[i]-=97; // 将所有字母转换为数字
    for(int i=1;i<=m;i++)t[i]-=97;
    h[0]=vector<pr>(26,pr(0,0));
    int p1=1,p2=1;
    for(int i=0;i<m;i++){
        (p1*=base1)%=mod1;
        (p2*=base2)%=mod2;
    }
    vector<pr>z(26,pr(0,0));
    for(int i=1;i<=m;i++){
        for(int j=0;j<26;j++){ // 计算 t 的哈希值数组
            z[j].fi=(z[j].fi*base1%mod1+(t[i]==j))%mod1;
            z[j].se=(z[j].se*base2%mod2+(t[i]==j))%mod2;
        }   
    }
    sort(z.begin(),z.end()); // 从小到大排序
    for(int i=1;i<=n;i++){ // 计算 s 的所有长为 k 的子串的哈希值数组
        h[i]=h[i-1];
        for(int j=0;j<26;j++){
            h[i][j].fi=(h[i][j].fi*base1%mod1+(s[i]==j))%mod1;
            h[i][j].se=(h[i][j].se*base2%mod2+(s[i]==j))%mod2;
            if(i>m)(h[i][j].fi+=mod1-p1*(s[i-m]==j)%mod1)%=mod1;
            if(i>m)(h[i][j].se+=mod2-p2*(s[i-m]==j)%mod2)%=mod2; // 类似滑动窗口，用上个 O(1) 推出下个
        }
    }
    for(int i=1;i<=n;i++){ // 排序
        sort(h[i].begin(),h[i].end());
    }
    int r=0;
    for(int i=m;i<=n;i++){ // 判断
        if(h[i]==z)++r;
    }
    return r;
}

:::