复习串的朴素模式匹配算法
模式匹配 ：
子串定位运算，在主串中找出子串出现的位置。
在串匹配中，将主串 s 称为目标(串)，子串 t 称为模式(串)。如果在主串 s 中能够找到子串 t， 则称匹配成功，返回 第一个 和 子串 t 中 第一个字符 相等 的 字符 在主串 s 中的 序号，否则，称匹配失败，返回 0。
算法思想：
从主串 s 的第 pos 个字符起和模式 t 的第一个字符比较之，若相同，则两者顺次的去比较后续的每一个字符，否则从主串 s 的下一个字符起再重新和模式 t 的字符比较之。 （为什么说它朴素，就是因为笨，因子串和主串的每躺比较，当发现匹配不对，则主串的指针要回溯到上次开始比较的字符处的下一个字符处，去重新比一遍！费劲）。
详细图解；
给定两个字符串，s 和 t，长度已知。
-》
初始 ab 相同，可以顺次比较，当3处，不匹配。则j 回溯到t1处，i 回到s 的下一个字符 s2处，从新开始和 t1比较。
-》
b 和 a又不匹配，j 回到1处（位置不变），i 回到下一个字符，也就是3处，继续比，匹配，顺次比较之。直到下面；
模式串的 j再次回溯到1，i 到4，继续比较，不匹配，t 的 j 继续回溯1，s的 i 继续到下一个字符，继续比较，直到 i=6，匹配
继续顺次比较，直到 t 比完，也就是在 j=5，i=10之后，j、i 继续++的时候，要判断出比完了，如图。这是整个过程。算法重要的是思想，理解思想，是第一步，脑子里有清晰的思路和完美的情景再现，那么代码实现都是水到渠成的事情。
用代码编写如下：
4
program ended with exit code: 0
分析时间复杂度
最坏的时候，最后匹配成功，比如，0000000000001 和 00001 ，比较每次都在00001的1开始不匹配，指针回溯到开头，主串也回溯 i-j+1，若模式子串的长度是m,目标串的长度是n，这时最坏的情况是每遍比较都在最后出现不等，即每遍最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法为 o（m*n），虽然，朴素的模式匹配，时间复杂度比较大，但是实际中，一般情况（除非模式串和主串之间存在很多的部分匹配的时候，因为此时每遍需要比较的次数很多，相乘不能近似），真正的执行时间是近似于o（n+m ）的，故当今仍然有他的用处！
辛苦的劳动，转载请注明出处，谢谢……
http://www.cnblogs.com/kubixuesheng/p/4322410.html