kmp模式Java编程需要学吗

发布网友发布时间：2022-05-15 18:00

共1个回答

热心网友时间：2023-08-05 03:12

kmp模式，是指进行字符串比较：
此算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现的，因此该算法被称为克努斯-莫里斯-普拉特操作，简称为KMP算法。
KMP算法，是不需要对目标串S进行回溯的模式匹配算法。读者可以回顾上面的例子，整个过程中完全没有对目标串S进行回溯，而只是对模式串T进行了回溯。通过前面的分析，我们发现这种匹配算法的关键在于当出现失配情况时，应能够决定将模式串T中的哪一个字符与目标串S的失配字符进行比较。所以呢，那三位前辈就通过研究发现，使用模式串T中的哪一个字符进行比较，仅仅依赖于模式串T本身，与目标串S无关。
这里就要引出KMP算法的关键所在next数组，next数组的作用就是当出现失配情况S[i] != T[j]时，next[j]就指示使用T中的以next[j]为下标的字符与S[i]进行比较（注意在KMP算法中，i是永远不会进行回溯的）。还需要说明的是当next[j] = -1时，就表示T中的任何字符都不与S[i]进行比较，下一轮比较从T[0]与S[i+1]开始进行。由此可见KMP算法在进行模式匹配之前需要先求出关于模式串T各个位置上的next函数值。即next[j]，j = 0,1,2,3,...n-1。
如果你是研究底层算法的话，要了解一下，如果你是做应用开发的话，了解一下就可以了，这是数据结构方面的内容。