/* * main.cpp * *  Created on: 2016年8月29日 *      Author: godsome */#include <iostream>#include <cstdio>#include <cstring>using namespace std;int next[100];int Index_KMP(char s[], char t[]){    int len_s = strlen(s), len_t = strlen(t);    int i = 0, j = 0;    while(i < len_s && j < len_t){        if(s[i] == t[j]){            i++;            j++;        }        else if(j == 0)            i++;        else            j = next[j-1] + 1;    }    if(j == len_t) return i - len_t;    else return -1;}void get_next(char str[], int next[]){    int len = strlen(str);    int i, j;    next[0] = -1;    for(i = 1; i < len; i++){        j = next[i-1];        while(str[j+1]!=str[i] && j>=0)            j = next[j];        if(str[i] == str[j+1])            next[i] = j + 1;        else            next[i] = -1;    }}int main(){    char *p = "ababcabcacbab";    char *t = "abcac";    get_next(t, next);    int pos = Index_KMP(p, t);    printf("%d\n", pos);    return 0;}