Well, it's crazy one =)

Let's solve this problem just like classical prefix-function solution, but let's get prefix-func from Z-function instead of using KMP. Here is a part of my code.


        z[0]=0;
        l=r=m=0;
        for(int i=1;i<n;i++)
        {
            if(i<r)
                z[i]=min(z[i-l],r-i+1);
            else
                z[i]=0;
            while(i+z[i]<n && t[i+z[i]]==t[z[i]])z[i]++;
            if(i+z[i]-1>r)
                l=i,r=i+z[i]-1;
        }
        fill(p,p+n,0);
        for(int i=0;i<n;i++)
            for(int j=0;j<z[i] && !p[i-j];j++)
                p[i-j]=z[i]-j;