题解 P5256 【编程作业 】

· · 题解

作业题。感觉比较灵活的题目，所以为什么这道题没有 KMP 标签啊？

题意

给定一个母串和一个模式串，其中小写字母需要建立一个一一对应的关系，然后将小写字母替换成对应的小写字母。问替换后的最大匹配数。

题解

我们模拟一下匹配，发现其实小写字母到底是什么字母根本不重要，比如说给定的模式串是 QabWabQa 还是 QqwWqwQq 本质是相同的，而小写字母真正不同的是它们的 mode 是相同的（瞎起的名字，就是字母排列的样式是一样的）。

先不考虑大写字母。如果两个串的 mode 相同，那么它们就是匹配的。而 mode 中真正重要的是几个相同的字母的位置关系，母串中相同的字母的位置 和 模式串中相同的字母的位置 应该保持一样。

怎么表示这种串中相同的字母的位置呢？有一种方法，即记录 a_i 为 i 到 s_i 上一次出现的距离。比如 abaabb 的 a 数组为 0,0,2,1,3,1 （如果前面没有那么就为 0）。两个小写字母的字符串匹配，当且仅当它们的 a 数组相同。

不过有一个问题，模式串中每个字母第一个出现的位置不应该是 0，否则可能会无法匹配。我们举个例子。母串为 aababa，模式串为 qwqw，那么母串的 a 数组为 0,1,0,2,2,2，模式串的 a 数组为 0,0,2,2，显然和母串 a 数组的后四位不能匹配。所以模式串中每个字母第一个出现的位置需要设一个“通配符”，即什么都能配上。

现在整个字符串中的小写字母都可以用数字或通配符去替代，于是我们把字符串替换后，再做一次 KMP 即可。KMP 时要注意改变匹配规则（通配符和数字）。

注意，通配符不代表所有都通配，否则你样例2都过不了。这个通配一定指可以通配这个区间中第一次出现的字符。可以具体看代码是怎么实现的。

bool same(int a,int b,int j) {
    if(a<0||b<0) return a==b;   //大写字母
    return a==b||(b==0&&a>j);   //小写字母 
}

j 代表匹配的长度，所以如果要用通用符我们必须保证这个 a 代表的字符 s 不是第一次出现，即 a>j。

接下来看代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;

char cs[N],ct[N];
int n,m,s[N],t[N],pre[29],nxt[N];

bool same(int a,int b,int j) {
    if(a<0||b<0) return a==b;           //大写字母
    return a==b||(b==0&&a>j);           //小写字母 
}
void kmp() {
    int j=0,ans=0; nxt[1]=0;
    for(int i=1;i<m;i++) {
        while(j&&!same(t[i+1],t[j+1],j)) j=nxt[j];
        if(same(t[i+1],t[j+1],j)) j++;
        nxt[i+1]=j;
    }
    j=0;
    for(int i=0;i<n;i++) {
        while(j&&!same(s[i+1],t[j+1],j)) j=nxt[j];
        if(same(s[i+1],t[j+1],j)) j++;
        if(j==m) ans++,j=nxt[j];
    }
    printf("%d\n",ans);
}

int main() {
    int Q; cin>>Q;
    while(Q--) {
        memset(ct,0,sizeof(ct)), memset(cs,0,sizeof(cs));
        memset(t,0,sizeof(t)), memset(s,0,sizeof(0));
        scanf("%s%s",cs+1,ct+1); n=strlen(cs+1), m=strlen(ct+1);
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=n;i++)               //预处理s串 
            if(cs[i]>='a'&&cs[i]<='z')
                s[i]=(pre[cs[i]-'a'+1]>0 ? i-pre[cs[i]-'a'+1] : 0),
                pre[cs[i]-'a'+1]=i;
            else s[i]=-(cs[i]-'A'+1);       //大写字母记为负数
        memset(pre,0,sizeof(pre));
        for(int i=0;i<=m;i++)               //预处理t串 
            if(ct[i]>='a'&&ct[i]<='z')
                t[i]=(pre[ct[i]-'a'+1]>0 ? i-pre[ct[i]-'a'+1] : 0),
                pre[ct[i]-'a'+1]=i;
            else t[i]=-(ct[i]-'A'+1);
        kmp();
    }
    return 0;
}