KMP(持续理解中...)

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);                  //没找到
}

// 生成最长前后缀数组
// 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
        {
            // 当前模式串 k 位置，已经不匹配。但 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