题解：P5256 [JSOI2013] 编程作业

· · 题解

从多倍经验来的但是被卡了，严肃更换做法。

双倍经验。

考虑 kmp，大写字母直接匹配，小写字母和种类无关，和同类的距离有关，考虑把一个点的权值设置为前面最近的同类的距离，显然权值完全匹配那么串就同构。

但是有的点前面没有同类，那么这里就会有一个通配符，一样做就好。

注意如果一个点的权值向前跳后对应点在串内，那么是不能和通配符匹配的，hack 见第二个样例。

时间复杂度线性。

#include<bits/stdc++.h>
using namespace std;
vector<int>pi(vector<int>s){
    vector<int>ret;
    ret.push_back(0);
    for(int i=1;i<s.size();i++){
        int flc=ret[i-1];
        while(flc&&s[flc]!=s[i]&&(s[flc]&&s[i]||min(s[flc],s[i])<0||s[i]<=flc))
        flc=ret[flc-1];
        if(s[i]==s[flc]||(s[flc]==0||s[i]==0)&&min(s[flc],s[i])>=0&&s[i]>flc)
        ret.push_back(flc+1);
        else ret.push_back(0);
    }
    return ret;
}
vector<int>kmp(vector<int>s,vector<int>t){
    vector<int>flc=t;
    flc.push_back(-114);
    for(int i:s)
    flc.push_back(i);
    vector<int>ret;
    vector<int>p=pi(flc);
    for(int i=0;i<p.size();i++){
        if(p[i]==t.size())
        ret.push_back(i+1-2*t.size());
    }
    return ret;
}
void solve(){
    map<char,int>mp;
    string s,t;
    cin>>s>>t;
    vector<int>v1,v2;
    for(int i=0;i<s.size();i++){
        if(s[i]<='Z')v1.push_back(-(s[i]-'A'+1));
        else if(!mp[s[i]])v1.push_back(0);
        else v1.push_back(i+1-mp[s[i]]);
        mp[s[i]]=i+1;
    }
    mp.clear();
    for(int i=0;i<t.size();i++){
        if(t[i]<='Z')v2.push_back(-(t[i]-'A'+1));
        else if(!mp[t[i]])v2.push_back(0);
        else v2.push_back(i+1-mp[t[i]]);
        mp[t[i]]=i+1;
    }
    cout<<kmp(v1,v2).size()<<'\n';
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 她老实且坦率无比地，说出了「我最讨厌你」。

// 说得十分亲昵。
// 说得十分友善。
// 说得十分开心。如此由衷的一句「我最讨厌你」。