题解：P5256 [JSOI2013] 编程作业

FS_NEO · 2025-11-11 23:56:24 · 题解

该复习 KMP 了。

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

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

/*

        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;
}