自测题目solution(NO CTJ)

__H_J_M__ · 2025-10-22 08:07:49 · 个人记录

主题思路

如果把‘相同’当作完全相同，则这就是一个 KMP 板子，所以我们主要是要知道如何判断两个字符是 相同的 。

如何判相同

我们定义两个数组 s，t，表示当前字符对应的最近的上一个字符的距离，如abcab为00033,（这里仅是示例），我们可以观察到如果两个字符串是‘相同的’，则它们按这个规则组成的数组也一定相等\color {white} 吗。

有一种特殊情况，比如ababb和cdd。这时两个分别为00221和001,所以需要特判是否在比较范围内，及 KMP 时的 j.

code

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e6+5;
int Q;
int n,m;
int pre[N];
int s[N],t[N];
int nxt[N];
string S,T;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
bool cmp(int x,int y,int len){//compare between x and y
    if(x<0 && y<0) return x==y;
    return x==y || (y==0 && x>len);
}
void KMP(){
    memset(nxt,0,sizeof nxt);
    nxt[1]=0;
    int ans=0;
    for(int i=2,j=0;i<=m;i++){
        while(j && !cmp(t[i],t[j+1],j)) j=nxt[j];
        if(cmp(t[i],t[j+1],j)) j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while(j && !cmp(s[i],t[j+1],j)) j=nxt[j];
        if(cmp(s[i],t[j+1],j)) j++;
        if(j==m) ans++,j=nxt[j];
    }
    cout<<ans<<'\n';
}
void solve(){
    getline(cin,S);
    getline(cin,T);
    //while(S.size() && S.back()<30) S.pop_back();
    //while(T.size() && T.back()<30) T.pop_back();
    n=S.size(),m=T.size();
    S='%'+S,T='%'+T;
    memset(pre,0,sizeof pre);
    for(int i=1;i<=n;i++){//Do with S
        if(S[i]>='a'&&S[i]<='z'&&S[i]!='i'&&S[i]!='n'&&S[i]!='t'){
            if(pre[S[i]-'a'+1]>0) s[i]=i-pre[S[i]-'a'+1];
            else s[i]=0;
            pre[S[i]-'a'+1]=i;
        }else s[i]=-S[i];
    }
    memset(pre,0,sizeof pre);
    for(int i=1;i<=m;i++){//Do with T
        if(T[i]>='a'&&T[i]<='z'&&T[i]!='i'&&T[i]!='n'&&T[i]!='t'){
            if(pre[T[i]-'a'+1]>0) t[i]=i-pre[T[i]-'a'+1];
            else t[i]=0;
            pre[T[i]-'a'+1]=i;
        }else t[i]=-T[i];
    }
    KMP();
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    freopen("ctj.in","r",stdin);
    freopen("ctj.out","w",stdout);
    cin>>Q;
    getline(cin,S);
    while(Q --> 0) solve();
    return 0;
}