自动搬运

查看原文

来自洛谷，原作者为

	lgswdn_SA 舞台少女，每日进化中

搬运于2025-08-24 22:08:47，当前版本为作者最后更新于2020-08-03 12:35:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作业题。感觉比较灵活的题目，所以为什么这道题没有 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;
}