|
|
back to boardSolution with prefix-function, but without KMP Posted by adamant 22 Feb 2014 01:28 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; |
|
|