KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特—莫里斯—普拉特算法。...KMP算法主要分为两个步骤:字符串的自我匹配,目标串和模式串之间的匹配。
?
KMP.jpg
(一)字符串的自我匹配
所谓字符串的自我匹配,就是看字符串中左右侧相等的最长子串的字符个数。...综上所述,字符串aaaa的自我匹配结果为0,1,2,3
例3:字符串abaabab
从最左边开始算起,a没有子串,匹配的字符个数为0;
ab左右侧没有相同的子串,匹配的字符个数为0;
aba...综上所述,字符串abaabac的自我匹配结果为0,0,1,1,2,3,2
从上面的3个例子中,咱们看看能否找到什么规律,这个规律可以使得咱们在字符串的自我匹配过程中不需要每次都从第一个字符开始比较呢?...以例3中的字符串str[]=”abaabab”为例,咱们将其自我匹配结果放进数组subCnt中,则subCnt[]={0,0,1,1,2,3,2}。