UVa problem solution 455 - Periodic Strings

problem link:


Discuss: in this problem you can find out longest common sub string using KMP. then trying divide length of string by(length-longest sub) if it's divide than longest sub will be result otherwise there is no result but n.

try yourself, before see the code.


#include<bits/stdc++.h>
using namespace std;
int matching(char T[],int n){

    int lcs[110];
    int j=0,i,cnt=0;
    lcs[0]=0;

    for(i=1; i<n; ){
        if(T[i]==T[j]){
                lcs[i]=j+1;
            i++;
            j++;
        }
        else{
            if(j!=0)
                j=lcs[j-1];
            else
            {

                lcs[i]=0;
                i++;
            }
        }
    }
    int z=0;
    for(i=0; i<n; i++){
        if(lcs[i]==0)
            z++;
    }
    for(i=n-1; i>=0; i--){
        cnt=n-lcs[i];
        if(n%cnt)
            return n;
            return cnt;
    }

}
int main()
{
      // freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin >>n;
    while(n--)
    {
        scanf("\n");
        char str[100],c[100];
        int i,j,cnt=0,flag=0,period[100],m;
        cin >>str;
        m=strlen(str);
        j=matching(str,m);
        cout <<j<<endl;
        if(n!=0)
        cout <<endl;
    }
    return 0;
}