SPOJ – FINDSR – Find String Roots

Problem NameFINDSR – Find String Roots
JudgeSPOJ
Problem Linkhttps://www.spoj.com/problems/FINDSR/
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()
{
    string s;
    while(cin>>s)
    {
        if(s=="*")break;
        ll len=s.size();
        ctPre(s);
        ll ans=len;
        ll val=len-pi[len-1];
        if(len%val==0)ans=val;
        cout<<(len/ans)<<"\n";
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error: Alert: Content is protected !!