T称为目标串（Target）或主串 ，P称为模式串（Pattren） 或子串
1、 简单字符串模式匹配算法
原理：用字符串P的字符依次与字符串T中的字符进行比较，首先将字符串P从第0个位置起与主串T的第pos个字符起依次进行比较对应字符，
如果全部对应相等，则表明已找到匹配，成功终止；否则将字符串P从第0个位置起与主串T的第pos+1个字符起依次进行比较对应字符，
过程类似。 如果直到匹配完主串T的所有字母 都没有找到，则匹配失败
2、首尾字符串模式匹配算法
原理：与简单字符串的基本原理相同，不同点是在 判断字符串是否相同的过程中，
简单字符串模式匹配算法 是按 第一个字符，第二个字符。。。。第n个字符的顺序进行对应匹配
首尾字符串模式匹配算法 是按 第一个字符，第n个字符，第二个字符，第n-1个字符的顺序进行匹配
造成前两个算法效率低的主要原因是在算法的执行过程中有回溯，而这些回溯都可以避免。比如：
T：abaabab
P：abab
假设pos=0 ，第一趟匹配的时候，t0=p0,t1=p1,t2=p2,t3!=p3,然而在模式串中p0!=p1，所以可以推知t1=p1!=p0，所以在第二趟的匹配中，将P右移一位，用t1与p0
比较一定不等，所以右移一位是无效位移。又因为p0=p2，所以t2=p2=p0，因此若直接将P右移两位，t2与p0的比较肯定是相等的，所以右移两位是有效位移。所以，KMP算法
在于寻找有效位移，跳过无效的比较，消除回溯。
3、KMP字符串模式匹配算法
假设第i+1趟的时候有 ti t(i+1).....t(i+j-1) = p0 p1 ...p(j-1) 且 p0 p1 ...p（j-2） != p1 p2 ...p(j-1)
可推知 t（i+1） t(i+2) ..t(i+j-1) = p1 p 2 ...p(j-1) != p0 p1 ...p（j-2）
所以第i+2趟 一定不匹配
以此类推
判断第i+3趟时，如果模式串P中 有 p0 p1 ...p（j-3）!= p2 p3 ...p(j-1) 则可推知 第i+3趟一定不匹配
故
直到对某值k，使得p
字符串匹配算法（在字符串T中查找是否有与字符串P相同的子串）
原文：http://www.cnblogs.com/wshyj/p/6306286.html