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;
}