求调(悬赏一个关注)
查看原帖
求调(悬赏一个关注)
594257
sad_desert楼主2022/8/1 16:49
#include<iostream>                       
#include<cstring>
using namespace std;
string c,a,d;
long long num[30],q,po,k,b[1000000],nxt[1000001],t[1000001];
bool sou(int a){
    for(int i=0;i<30;i++)
        if(num[i]==a)
            return 1;
    return 0;       
}
int main() {
    getline(cin,c);
    getline(cin,d);
    for(int i=0;i<c.size();i++){
        if(c[i]=='$')
            break;
        if(c[i]!=' '){
            a+=c[i];
        }
    }
    k=0;
    for(int i=0;i<d.size();i++){
        if(c[i]=='$')
            break;
        if(d[i]!=' '){
            if((num[d[i]-'a'])==0){
                b[k++]=++po;
                num[d[i]-'a']=po;
            }else{
                b[k++]=num[d[i]-'a'];
            }
        }
    }

    for (int i=1, j=0;i<k; j=nxt[++i]) {
        while (j&&b[i]!=b[j])j=nxt[j];
        if (b[i]==b[j])nxt[i+1]=j+1;
    }
    for(int i=0,j=0;i<a.size();++i){
        for(int pp=j+1;pp<30;pp++)
            num[pp]=0;
        if(num[a[i]-'a']==0){
            t[i]=b[j];
            if(sou(b[j]))
                continue;
            num[a[i]-'a']=b[j];
        }
        else{
            t[i]=num[a[i]-'a'];
        }
        while(j&&t[i]!=b[j])
            j=nxt[j];
        if(t[i]==b[j])
            ++j;
        if(j==k){
            cout<<i-k+2<<endl;
            return 0;
        }
    }
    return 0;
}
2022/8/1 16:49
加载中...