static void Main()
{
    Console.WriteLine(KMP("1111ababacae22", "ababacae"));
    Console.ReadLine();
}

static int KMP(String s, String t)
{
    int[] next=new int[t.Length];
    int i = 0; 
    int j = 0;
    Getnext(next,t);
    while (i < s.Length && j < t.Length)
    {
        if (j == -1 || s[i] == t[j])
        {
            i++;
            j++;
        }
        else j = next[j];   // j = next[j]。此舉意味著失配時，接下來模式串 t 要相對于主串S向右移動j - next [j] 位   ①        
    }
    if (j >= t.Length)
        return (i - t.Length);         //匹配成功，返回子串的位置
    else
        return (-1);                  //沒找到
}

// 生成最長前后綴數(shù)組
// ababacae
// -1, 0, 0, 1, 2, 3, 0, 1
static void Getnext(int[] next, String t)
{
    int j = 0;
    int k = -1;
    next[0] = -1;

    while (j < t.Length - 1)
    {
        if (k == -1 || t[j] == t[k])
        {
            j++; 
            k++;
            next[j] = k;
        }
        else
        {
            // 當(dāng)前模式串 k 位置，已經(jīng)不匹配。但 k 位置之前的子字符串中存在 next[k] 個最長前后綴。
            // 因此，將 k 回溯到 next[k] 處 ②
            k = next[k];  
        }
    }
}

① 的理解
可以理解為：模式串 t 的 k 位置要與主串 s 的 j 位置對齊，用于比較

image.png

=>

image.png

②的理解

image.png

參考文檔
https://blog.csdn.net/yyzsir/article/details/89462339