Python版

def kmp_search(string, patt):
    next = build_next(patt)  # 假设我们已经算出了next数组
    i = 0  # 主串中的指针
    j = 0  # 子串中的指针
    while i < len(string):
        if string[i] == patt[j]:  # 字符匹配，指针后移
            i += 1
            j += 1
        elif j > 0:  # 字符失配，根据next跳过子串前面的一些字符
            j = next[j - 1]
        else:  # 子串第一个字符就失配
            i += 1
        if j == len(patt):  # 匹配成功
            return i - j


def build_next(patt):
    """
    计算next数组
    """
    next = [0]  # next数组（初值元素一个0
    prefix_len = 0  # 当前共同前后缀的长度
    i = 1
    while i < len(patt):
        if patt[prefix_len] == patt[i]:
            prefix_len += 1
            next.append(prefix_len)
            i += 1
        else:
            if prefix_len == 0:
                next.append(0)
                i += 1
            else:
                prefix_len = next[prefix_len - 1]
    return next


if __name__ == "__main__":
    s = "hello world!"
    s1 = "world"
    index = kmp_search(s, s1)
    print(index)

C版

#include<stdio.h>
#include<string.h>
#define NEXT_MAX 100
int* builed_next(char patt[])
{
    //计算next数组
    int next[NEXT_MAX] = { 0 };
    int prefix_len = 0;
    int i = 1;
    while (i < strlen(patt))
    {
        if (patt[prefix_len] == patt[i])
        {
            prefix_len++;
            next[i] = prefix_len;
            i++;
        }
        else
        {
            if (prefix_len == 0)
                next[i] == 0, i++;
            else
                prefix_len = next[prefix_len - 1];
        }
    }
    int* p = next;
    return p;
}
int kmp_search(char string[], char patt[])
{
    int* next = builed_next(patt);
    int i = 0, j = 0;
    while (i < strlen(string))
    {
        if (string[i] == patt[j])
            i++, j++;
        else if (j > 0)
            j = next[j - 1];
        else
            i++;
        if (j == strlen(patt))
            return i - j;
    }
}
int main()
{
    char s[] = "hello world!";
    char s1[] = "world";
    int index = kmp_search(s, s1);
    printf("%d", index);
}

C++版

#include<iostream>
#include<string>
#define NEXT_MAX 100
using namespace std;
int * builed_next(string patt)
{
    //计算next数组
    int next[NEXT_MAX] = { 0 };
    int prefix_len = 0;
    int i = 1;
    while (i < patt.length())
    {
        if (patt[prefix_len] == patt[i])
        {
            prefix_len++;
            next[i] = prefix_len;
            i++;
        }
        else
        {
            if (prefix_len == 0)
                next[i] == 0, i++;
            else
                prefix_len = next[prefix_len - 1];
        }
    }
    int* p = next;
    return p;
}
int kmp_search(string s, string patt)
{
    int* next = builed_next(patt);
    int i = 0, j = 0;
    while (i<s.length())
    {
        if (s[i] == patt[j])
            i++, j++;
        else if (j > 0)
            j = next[j - 1];
        else
            i++;
        if (j == patt.length())
            return i - j;
    }
}
int main()
{
    string s = "hello world!";
    string s1 = "world";
    int index = kmp_search(s, s1);
    cout << index;
}