Spoj FINDSR - Find String Roots Solution
#include<bits/stdc++.h> using namespace std; void arraycal(string pat, int M, int lps[]) { int len = 0; lps[0] = 0; int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len-1]; } else { lps[i] = 0; i++; } } } } int main() { string s; cin>>s; while(s!="*") { int m=s.size(),i; int lps[m]; arraycal(s,m,lps); int x= m-lps[m-1]; if(m%x==0) cout<<m/x<<"\n"; else cout<<"1"<<"\n"; cin>>s; } return 0; }