-
Notifications
You must be signed in to change notification settings - Fork 26
KMP getNext()
字符串模式匹配,普通模式非常好理解,拿着模式串依次与主串做比较,知道完全匹配,但是这种算法,主串得不断地回溯,时间复杂度O(n*m)。
唐纳德·克努特
有没有降低时间复杂度的可能,唐纳德·克努特等人想到了一种办法不用使主串不停地回溯,而每次使模式串的某个字符与主串的待比较字符对齐,这个算法简称KMP。求解模式串的哪个字符该与这次比较的主串字符对齐,是KMP算法的核心,简称next函数或失配函数。这种算法求解复杂度降低到O(n+m)。
next[j]=k表达的意思是从模式串的 1~j-1 组成的子模式串,最长相同的前、后缀的长度为 k-1。举例说明,如下的字符串,next[6]=3,因为编号为6的字符c的最长前缀为编号为1的a ,编号为2的b 字符,最长后缀为编号为4的字符,编号为5的字符b,所以 k=3。 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |:---:|:---:|:---:|:---:|:---:|:---:| | a | b | a | a | b | c | a | c |
再看一下失配函数*next[j]*的严格定义,模式串字符的编码从1开始。
这里写图片描述
next 函数值仅取决于模式串本身而与相匹配的主串无关。从next函数的定义出发用递推的方法求next函数值。
由定义得知 next[1]=0,设next[j]=k,这表明在模式串中存在下列关系
"P1...Pk-1" = "Pj-k+1...Pj-1"
图形化显示(一条竖线表示一个字符):
这里写图片描述
其中k为满足1 < k < j的某个值,并且不能存在k' > k满足上个等式。此时 next[j+1]=? 分两种情况讨论,
1)若 Pk = Pj ,则 next[j+1] = next[j] + 1 ,即 k + 1 ,如下图显示:
这里写图片描述
2)若Pk不等于Pj,如下图所示,我们把如下字符,看成一个字符串,寻找它的最长相同的前、后缀:
"P1...Pj+1"
这里写图片描述
此时我们已知一个条件:
"P1...Pk-1" = "Pj-k+1...Pj-1"
也就是在上图中2个黄色区域表示的前、后缀字符串相等,这样我们依然在上图中的左侧黄色部分中寻找。最终找到了2块咖啡色区域 1(削除) k'-1, k-k'+1 (削除ここまで)k-1 相等,根据next函数的定义,便是:
next[k]=k'
这里写图片描述
并且我们根据已知条件 'P1...Pk-1' = 'Pj-k+1...Pj-1',可以推导出在右侧黄色区域也存在这样的咖啡色区域,根据等式传递,我们可以得出:
"P1...Pk'-1" = "Pj-k'+1...Pj-1"
因为Pj不等于Pk,所以我们新找出了一个k'(很显然1 < k' < k),如果它真的满足了 Pj=Pk',则 next[j+1] = k' + 1 ,即 :
next[j+1] = next[k] + 1
如果它很遗憾地又不等于Pj,也没关系,我们继续在[1,k']这个区间内找这样的K点,如果真的不存在这样的k',那么 根据定义可以得出:
next[j+1]=1
/// <summary> /// 失配函数 /// </summary> /// <param name="p">模式字符串(编码从索引位置1开始)</param> /// <returns>模式字符串中每个字符的失配值数组</returns> private int[] getNext(char[] p) { int[] next = new int[p.Length]; next[1] = 0; int j = 1; int k = 0; while (j < p.Length - 1) { if (k == 0 || p[j] == p[k]) { next[++j] = ++k; //上述分析中的k'+1赋值给next[j+1] } else { k = next[k]; //next[k]赋值给k,相当于上述分析中的k' } } return next; }
模拟失配函数求解的整个过程代码。
static void Main(string[] args) { string pattern = "abaabcac"; char[] pcharsfrom1 = preOperate(pattern); Console.WriteLine(); int[] next = getNextWithTest(pcharsfrom1); printf(next); Console.ReadLine(); }
预处理字符串,将字符串整体后移1位
/// <summary>
/// 预处理字符串,将字符串整体后移1位
/// </summary>
/// <returns></returns>
private static char[] preOperate(string pattern)
{
char[] pchars = pattern.ToCharArray(0, pattern.Length);
char[] pcharsfrom1 = new char[pchars.Length + 1];
for (int i = pchars.Length; i > 0; i--)
pcharsfrom1[i] = pchars[i - 1];
return pcharsfrom1;
}
private static int[] getNextWithTest(char[] p) { int[] next = new int[p.Length]; next[1] = 0; int j = 1; int k = 0; printf(p); while (j < p.Length - 1) { if (k != 0) Console.WriteLine("p[{0}]({1}) == p[{2}]({3})??", j, p[j], k, p[k]); if (k == 0 || p[j] == p[k]) { if (k == 0) { ++j; ++k; next[j] = k; Console.WriteLine("根据k=0得出:p[{0}]={1}", j, k); Console.ForegroundColor = ConsoleColor.DarkGreen; Console.WriteLine("--------------------------------"); Console.ForegroundColor = ConsoleColor.White; } else { ++j; ++k; next[j] = k; Console.WriteLine("根据p[j] == p[k]得出:p[{0}]={1}", j, k); Console.ForegroundColor = ConsoleColor.DarkGreen; Console.WriteLine("--------------------------------"); Console.ForegroundColor = ConsoleColor.White; } } else { k = next[k]; } } return next; } private static void printf<T>(T[] p) { int eachlineCount = 10; for (int line = 0; line < p.Length / eachlineCount + 1; line++) { for (int i = 0; i < eachlineCount && line * eachlineCount + i < p.Length; i++) { Console.Write(" {0} ", line * eachlineCount + i); } Console.Write("\n"); for (int i = 0; i < eachlineCount && line * eachlineCount + i < p.Length; i++) { if (line == 0) Console.Write(" {0} ", p[line * eachlineCount + i]); else { Console.Write(" {0} ", p[line * eachlineCount + i]); } } Console.Write("\n\n"); } }
模拟结果展示:
这里写图片描述
源码下载:
I love LeetCode.