c/c++程序之_KMP字符串模式匹配详解

KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。先来看一个简单匹配算法的函数:此算法的思想是直截了当的:将主串S中某个位置i起始的子串和模式串T相比较。即从 j=0起比较S[i+j]与T[j],若相等,则在主串S中存在以i为起始位置匹配成功的可能性,继续往后比较( j逐步增1),直至与T串中最后一个字符相等为止,否则改从S串的下一个字符起重新开始