10298 - Power Strings

10298 - Power Strings

Discuss: this is simple string matching problem. in this problem you have asked to how many reputation you need to make the string. for that i do is create a longest common sequence array. which suffix and also prefix of the string. and if n-l divide n then it can form with this sub string. and the reputation is need n/(n-l). just simple do it.

try yourself,before see the code


 #include<bits/stdc++.h>
using namespace std;
int Power(string str,int n){
    int i,j=0,lcs[10000005],l;
    lcs[0]=0;
    for(i=1; i<n; ){
        if(str[i]==str[j]){
            lcs[i]=j+1;
            i++;
            j++;
        }
        else{
            if(j!=0)
                j=lcs[j-1];
            else
            {
                lcs[i]=0;
                i++;
            }
        }
    }
  //  for(i=0; i<n; i++)
     //  cout <<lcs[i]<<' ';
    //cout <<endl;
    for(i=n-1; i>=0; i--){
        l=n-lcs[i];
       if(n%l==0)
            return (n/l);
    }
return 0;

}
int main()
{
     // freopen("input.txt","r",stdin);
     // freopen("out.txt","w",stdout);
    string str;
    while(cin >>str)
    {
        int n;
        if(str[0]=='.')
            break;
      n=str.length();
      cout <<Power(str,n)<<endl;
      str.clear();
    }
    return 0;
}