串2 串的模式匹配算法（KMP）

#include <stdio.h>

#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN + 1];

void get_next(SString T, int next[]){
    int i = 1, j = 0;
    next[1] = 0;
    while(i < T[0]){
        if(j == 0 || T[i] == T[j]){
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

void get_nextval(SString T, int nextval[]){
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0]){
        if(j == 0 || T[i] == T[j]){
            ++i;
            ++j;
            if(T[i] != T[j])    nextval[i] = j;
            else    nextval[i] = nextval[j];
        }
        else    j = nextval[j];
    }
}

int Index_KMP(SString S, SString T, int pos){
    int i = pos, j = 1;
    int N = T[0];
    int next[N];
    get_nextval(T, next);        //可以替换为getnext() 
    
    while(i <= S[0] && j <= T[0]){
        if(j == 0 || S[i] == T[j]){
            ++i;
            ++j;
        }
        else
            j = next[j];
        
    }
    if(j > T[0])    return i - T[0];
    else    return 0;
}

void StrAssign(SString S, char str[]){
    int i = 0;
    char * c = str;
    while (* c != '\0'){
        c++;
        i++;
    }
    S[0] = i;
    for(int j = 1; j <= i; j++){
        S[j] = str[j - 1];
    }
}

int main(){
    char a[] = "acabaabaabcacaabc";
    char b[] = "abaabcac";
    
    SString S, T;
    StrAssign(S, a);
    StrAssign(T, b);
    
    int pos = Index_KMP(S, T, 1);
    printf("%d", pos);
    
    return 0;
}