Problem Name | String Tale |
Judge | Timus |
Problem Link | https://acm.timus.ru/problem.aspx?space=1&num=1423&locale=en |
Algorithms & DS | Prefix 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;
}
Code language: PHP (php)