Timus – String Tale

T
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; }
Code language: PHP (php)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!