这个题可以增进对NEXT数组的理解,next【k】表示这个k前面有next【k】个字符和从0开始的k个字符相等,那么我们只要从最后开始查找,
先查找next【len】,然后找到了最长的那个,然后x=next【len】,查找next【x】,为什么从前面查找等价于从后面呢?
因为next【len】表示最后面的len个和最前面的next【len】个相等的,在前面找,相当于在后面查找。
把next数组开成了char类型,浪费了半个小时。揪心
#include<stdio.h> #include<string.h> #define val 400008 char p[val]; int next[val]; void output(int); void set_next(); int lenp; int main() { int i; while(scanf("%s",p)!=EOF) { lenp=strlen(p); set_next(); output(lenp); printf("%d\n",lenp); } return 0; } void set_next() { int j,k; j=0,k=-1; next[j]=k; while(j<lenp) { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } void output(int k) { if(next[k]==0) return ; output(next[k]); printf("%d ",next[k]); }