串

        串（string）是由零个或多个字符组成的有限序列，又名字符串。

模式匹配

        子串的定位操作通常称作串的模式匹配

1、朴素模式匹配算法

        以从主串S=“goodgoogle”中找到T=“google”这个子串的位置。

2、KMP模式匹配算法

        如果有多个0和1重复字符的字符串，挨个遍历的算法是非常糟糕的事件。一个可以大大避免遍历的算法——KMP算法。如果主串S=“abcdefgab”,匹配的T=“abcdex”。如果用朴素算法的话，前五个字母，两个字符串完全相等，知道第六个字母，f和x不相等。

按照朴素模式匹配算法，应如上图的流程2、3、4、5、6。即主串S中当i=2、3、4、5、6时，首字符与子串T的首字符均不等。仔细观察发现，对于要匹配的子串T来说，"abcdex"首字符"a"与后面的串"bcdex"中任意一个字符都不相等。对于上图流程1来说，前五位字符分别相等，意味着子串T的首字符"a"不可能与S串的第二位到第五位的字符相等。所以上图流程2、3、4、5的判断都是多余。