题解：P5256 [JSOI2013] 编程作业

该复习 KMP 了。

考虑如何判断两个串一样。对于 A 串的小写字母集合，若存在一种映射，将字母通替换后变成 B 串，则 A,B 串一样。而大写字母不能有任何区别。维护每个位置

i

到上一次该字母出现位置的距离

a_i

即可。

匹配的时候要注意，模式串中首次出现的字母，对应主串位置可能并非首次出现。显然这时其实可以匹配上，则将模式串上首次出现字母的位置设为万能字符。观察样例三，发现万能字符使用还是有限制的：只能与目前匹配串内每种小写字符首次出现的位置匹配。具体策略见代码。

CPP


/*

		2025.11.11

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int>P;
const int MAXN=1000005;
string a,b;
int aa[MAXN],bb[MAXN],t[MAXN];
int nxt[MAXN],n,m;
bool diff(int x,int y,int z){
	if(x<0||y<0)return x!=y;
	if(x==y)return 0;
	if(y==0&&x>z)return 0;
	return 1;
}
void solve(){
	cin>>a>>b;n=a.size(),m=b.size();a=" "+a,b=" "+b;
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++){
		if(a[i]>='a'&&a[i]<='z'){
			if(t[a[i]])aa[i]=i-t[a[i]],t[a[i]]=i;
			else aa[i]=0,t[a[i]]=i;
		}
		else aa[i]='A'-1-a[i];
	}
	memset(t,0,sizeof(t));
	for(int i=1;i<=m;i++){
		if(b[i]>='a'&&b[i]<='z'){
			if(t[b[i]])bb[i]=i-t[b[i]],t[b[i]]=i;
			else bb[i]=0,t[b[i]]=i;
		}
		else bb[i]='A'-1-b[i];
	}
	nxt[1]=0;int ans=0;
	for(int i=2,j=0;i<=m;i++){
		while(j>0&&diff(bb[i],bb[j+1],j))j=nxt[j];
		if(!diff(bb[i],bb[j+1],j))j++;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=n;i++){
		while(j>0&&diff(aa[i],bb[j+1],j))j=nxt[j];
		if(!diff(aa[i],bb[j+1],j))j++;
		if(j==m)j=nxt[j],ans++;
	}
	cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

题解：P5256 [JSOI2013] 编程作业

文章操作

相关推荐

评论

题解：P5256 [JSOI2013] 编程作业