这篇文章上次修改于 444 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
本文共 1978 个字，阅读时长 ≈ 5 分钟

11.3 C. 模糊匹配（match）

哈希好题

题意

如果两个字符串只有第 i 位不同，那么就称他俩为模糊匹配。给你 n 个字符串，问有多少对模糊匹配的字符串

思路

先想暴力，考虑枚举不同的位数然后暴力匹配，时间复杂度 $O(n^2l^2)$（ l 为字符串长度），枚举两个字符串为 $n^2$，枚举位数 $l$，暴力匹配 $l$

考虑优化，想到可以枚举两个字符串并统计它们不同字符的个数，这样可以优化掉一个 $l$。

赛时代码 $O(n^2l)$：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#ifdef ONLINE_JUDGE
#define debug(x)
#else
#define debug(x) cout<<' '<<#x<<'='<<x<<endl
#endif
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=30004;
int n,l;
string s[N];
int main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>l;
    for(int i=1;i<=n;++i){
        cin>>s[i];
    }
    int ans=0;
    bool diff=0;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            diff=0;
            for(int k=0;k<l;++k){
                if(s[i][k]!=s[j][k]&&diff){
                    diff=0;
                    break;
                }
                if(s[i][k]!=s[j][k]&&!diff) diff=1;
            }
            if(diff) ++ans;
        }
    }
    cout<<ans<<endl;
    return 0;
}

想想怎么匹配，考虑用哈希维护字符串，将第一个暴力的 $O(l)$ 匹配换成 $O(1)$ 匹配，这样就变成了 $O(n^2l)$，再想怎么优化枚举，考虑开一个桶存储删完第 i 位后字符串的种类，然后用等差数列通项公式计算答案即可，这样的话就变成了 $O(nl)$ ，桶可以用 unordered_map 统计这样一次操作就是 $O(1)$ 的，可以通过。

但是std不愧是std，std的写法为将枚举到的第 i 位变为 0，并将改后的数组排序，这样能保证计算答案的时候能直接计算到一样的，然后遍历一遍数组并计算答案，时间复杂度一样，但是实现更简单。

代码

只写了std写法：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define int unsigned long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=30004,base=131;
int n,m;
string s[N];
int a[N],t[N],mi[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    mi[0]=1;
    for(int i=1;i<=m;++i) mi[i]=mi[i-1]*base;
    for(int i=1;i<=n;++i){
        cin>>s[i];
        for(int j=0;j<m;++j){
            //哈希
            a[i]=a[i]*base+s[i][j]-'a'+1;
        }
    }
    int ans=0;
    for(int j=0;j<m;++j){
        for(int i=1;i<=n;++i){
            //将枚举到的那一位置0
            t[i]=a[i]-(s[i][j]-'a'+1)*mi[m-j-1];
        }
        //排序统计答案
        sort(t+1,t+1+n);
        int tmp=1;
        for(int i=1;i<n;++i){
            if(t[i]!=t[i+1]) tmp=1;
            else{
                ans+=tmp;
                ++tmp;
            }
        }
    }
    printf("%Ld\n",ans);
    return 0;
}