字符串next和nextval值的计算
针对字符串ababaabab，计算next和nextval的值。


第一行是序号，从0开始。


第二行是字符串的元素


第三行是next值，为当前位置前面字符串收尾重复的最长字符个数。


第四行是nextval值，当以next和以i为索引的字符不相同时，nextval值就是next值。当两个字符相同时，nextval值是以next为索引的nextval值。


next 值的计算
举个例子，当i=5时，计算方法如下：

其中，0和1的next值固定为-1和0.
nextval值的计算
0的nextval值固定为-1。




i
0
1
2
3
4
5
6
7
8




s
a
b
a
b
a
a
b
a
b


next
-1
0
0
1
2
3
1
2
3


nextval
-1
0
-1
0
-1
3
0
-1
0


有时候下标从1开始，则nextval就是010104101.

题目描述

字符串的子串定位称为模式匹配，模式匹配可以有多种方法。简单的算法可以使用两重嵌套循环，时间复杂度为母串与子串长度的乘积。而KMP算法相对来说在时间复杂度上要好得多，为母串与子串长度的和。但其算符比较难以理解。

在KMP算法中，使用到了一个next数组。这个数组就是在比较失配时母串指针不必回溯，而子串指针移动相应位置即可。请参考教材next数组的计算公式与算法，编程实现之。

输入

一个模式串，仅由英文小写字母组成。长度不大于100。

输出

输出模式串对应的移动数组next。每个整数后跟一个空格。

样例输入 Copy

abaabcac

样例输出	Copy

0 1 1 2 2 3 1 2
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char a[105];
char b[105];
int next[105];
int L1, L2;

void f()
 {
    int i=0,j=-1;
    next[0]=-1;
    while(i<strlen(a)){
        if(j==-1||a[i]==a[j]){
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
     }
 }


int main()
{
    int i;
    scanf("%s", a);
    f();
    for(i=0;i<strlen(a);i++)
        printf("%d ",next[i]+1);
       
    return 0;
}

//next数组中的值val有两种情况：
//1、val=-1；此时意味着主串和子串的下标都需要加1；
//2、val={0,1...k-1}中的任意值，k为正在比较的第k个字符，也就是说当他们不相等时，需要回溯到val继续比较；
void get_next(char *p,int n) {
    int i=0,k;
    k=next[0]=-1;//k表示当前i字符的next值,利用i求i+1的next
    while(i<n) {
        if(k==-1||p[i]==p[k]) {
            k++,i++;
            next[i]=k;//但是当i+1与他的next值对应的字符相等时，我们需要继续改进next[i]=next[k];
        } else k=next[k];
    }
}
void get_nextval(char *p,int n) {
    int i=0,k;
    k=next[0]=-1;//k表示当前i字符的next值,利用i求i+1的next
    while(i<n) {
        if(k==-1||p[i]==p[k]) {
            k++,i++;
            if(p[i]==p[k]) next[i]=next[k];
            else next[i]=k;
        } else k=next[k];
    }
}

　　KMP算法相比于朴素的模式匹配算法，其改进之处在于：利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离。该算法的关键在于next函数的计算，next函数的定义如下： 

 

　　我们介绍一种简便的求解next数组的方法，其主要思想是： 

　　模式串为M，定义一个变量ch 

①若M[ch] = M[i-1]，则next[i++] = ++ch（即next[i]=ch+1，并将原来的i和ch自增1） 

②若M[ch] ≠ M[i-1]，则令ch=next[ch]，再进行比较，直至相等，处理方法同① 

③若执行②到最后仍没有相等的结果，即M[0]仍≠M[i-1]，则令ch = 0，next[i++] = 0 

这么说可能比较抽象，我们来具体的看一个实例： 

模式串为abababb，求其next数组 

 

注意：我们的next数组的公式中规定j=0时next=-1，其他情况等于0，所以next数组的前两个元素为-1和0，若定义改变则此处也应做相应改变 

再看一个例子，abacc：