学步园

【DEV-C工程】什么都不说，直接上代码。

#include <stdio.h>
#include <stdlib.h>
 
char str_a[22] = "abcabcddacdabcdbabadac";
char str_b[7] = "abcdbab";
 
int next[7] = {-1};
 
void Next(char *str, int len)
{
    int i, k;
     
    next[0] = -1;
    for (i = 0; i < len - 1; i++) {
        k = next[i];
        if (str[i + 1] == str[k + 1]) {
            next[i + 1] = k + 1;
        }
        else {
            if (k == -1)
                next[i + 1] = -1;
            else
                next[i + 1] = next[k];
        }
    }
}


int kmp(char *s, char *p, int n, int m)
{
    int i, j;
    
    Next(p, m);
    i = j = 0;
    while (i < n && j < m) {
        if (s[i] == p[j])
			j++;
        else {
            if (j != 0)
                j = next[j - 1] + 1;
        }
        i++;
    }
    
    if (j < m)
        return -1;
    return i - m;
}


int main(int argc, char *argv[])
{
    printf("%d\n", kmp(str_a, str_b, 22, 7));
    
    system("PAUSE");
    return 0;
}