1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>
int next[10005];//if jth charactar failed the match
char pat[10005];
char txt[1000005];
void init(char str[], int len)
{
    int i,j;
    memset(next,-1,(len+1)*sizeof(int));
    next[0] = 0;
    //next[1] = 0;
    j = 0;
    i = 1;
    while (1)
    {
        //printf("i:%d  j:%d\n",i,j);
        if (next[i] == -1)
        {
            next[i] = j;
        }
        if (i == len)
        {
            break;
        }
        if (str[i] == str[j])
        {
            //next[i] = j;
            //next[i] = j;
            i++;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX