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
