C角度——任何 C程序，可理解为指针指向某一个字符，然后字符匹配。

1）字符匹配的历史

2）字符匹配算法

3）程序实现

4）应用及笔试题分析

一.简单匹配算法

例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1]和T[1]是否相等…我们发现一直比较到S[5]和T[5]才不等。如图：

当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：

这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。

简单匹配算法的最坏情况是，假设源字符串S有m个字符，目标字符串T有n个字符，则最坏情况是比较(m-n)*n次，即在源字符串末尾处匹配到。如何提出更“智能”，更有“记忆力”的算法呢？请看大名顶顶的D.E.K等提出的KMP算法。

二、KMP算法