Timus – String Tale

Problem NameString Tale
JudgeTimus
Problem Linkhttps://acm.timus.ru/problem.aspx?space=1&num=1423&locale=en
Algorithms & DSPrefix Function, KMP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll>pi;
void ctPre(string s)
{
    ll len=s.size();
    pi.resize(len+5);
    pi[0]=0;
    for(ll i=1;i<len;i++){
        ll j=pi[i-1];
        while(j>0&&s[i]!=s[j])j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
}

int main()
{
    ll n;
    cin>>n;
    string pt,s;
    cin>>pt>>s;
    s+=s;
    ll ptlen=pt.size();
    pt+=" ";
    pt+=s;
    ll len=pt.size();
    ctPre(pt);
    ll ans=-1;
    for(ll i=ptlen+1,j=0;i<len;i++,j++){
        if(pi[i]==ptlen){
            ans=j-ptlen+1;
            break;
        }
    }
    cout<<ans<<"\n";
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error: Alert: Content is protected !!