複習串的樸素模式比對算法
模式比對 ：
子串定位運算，在主串中找出子串出現的位置。
在串比對中，将主串 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