【BZOJ4462】【JSOI2013】—编程作业（KMP）

传送门

---

考虑小写字母置换不好匹配，但是同一种字母是有相同的置换

考虑如果把小写字母的值变成和前一个相同字母的距离
就可以正常的匹配了

$Kmp$即可
注意特判第一个字符的情况

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
	char ch=gc();
	int res=0,f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const int N=1000005;
int fail[N],a[N],vis[N],b[N],n,m;
char s[N];
inline bool iscap(char c){
	return c>='A'&&c<='Z';
}
inline bool check(int x,int y,int l){
	return x==y||(x>l&&y>l);
}
int main(){
	int T=read();
	while(T--){
		memset(vis,0,sizeof(vis));
		memset(a,0,sizeof(a));
		memset(fail,0,sizeof(fail));
		memset(b,0,sizeof(b));
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=1;i<=n;i++)
		if(iscap(s[i]))a[i]=-s[i];
		else a[i]=i-vis[s[i]],vis[s[i]]=i;
		scanf("%s",s+1);
		m=strlen(s+1);
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++)
		if(iscap(s[i]))b[i]=-s[i];
		else b[i]=i-vis[s[i]],vis[s[i]]=i;
		for(int i=0,j=2;j<=m;j++){
			while(i&&!check(b[i+1],b[j],i))i=fail[i];
			if(check(b[i+1],b[j],i))i++;
			fail[j]=i;
		}
		int res=0;
		for(int i=0,j=1;j<=n;j++){
			while(i&&!check(b[i+1],a[j],i))i=fail[i];
			if(check(b[i+1],a[j],i))i++;
			if(i==m)i=fail[i],res++;
		}cout<<res<<'
';
	}
}