kmp

void getnext(char a[], int next[], int n)
{
        int i, j;

        i = 1;
        j = 0;
        next[0] = -1;
        while (i < n) {
                if (-1 == j || a[i] == a[j]) {
                        i++;
                        j++;
                        if (a[i] != a[j])
                                next[i] = j;
                        else
                                next[i] = next[j];
                } else
                        j = next[j];

        }
}

int substr(char str[], char a[])
{
        int i, j;
        int n;
        int *next;

        n = strlen(a);
        next = malloc(n * sizeof(int));
        getnext(a, next, n);
        i = 0; j = 0;

        while (str[i] != '\0' && j < n) {   //  到str末尾 或者匹配成功
                if (j == -1 || str[i] == a[j]) {
                        i ++;
                        j ++;
                } else
                        j = next[j];
        }

        free(next);
        if (j == n)
                return i - n;
        else
                return -1;
}

另一种getnext的方法

void getnext(char a[], int next[], int n)
{
        next[0] = -1;
        for (int i=1; i<n; i++) {
                next[i] = 0;
        }

        for (int i=1; i<n; i++) {
                if (a[i] == a[0]) {
                        next[i] = next[i]==0 ? -1 : next[i];
                        int k = 1;
                        int h = i+1;
                        while (h<n && a[k]==a[h]) {
                                h++;
                                k++;
                        }
                        if (h < n) {
                                next[h] = k;
                        }
                }
        }
}