[LeetCode] Implement strStr() [18]

題目

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

原題連結（點我）

解題思路

字元串比對這也是個老題了，方法主要有下面4種，

1. 暴利破解法（BF），這個沒啥說的，就是一輪一輪的比較，知道遇到相比對的，這個的時間複雜度為O(n^2)。

2. KMP，這應該是字元串比對領域中最長聽說的算法了吧。

3. Horspool算法，這個不常聽說，但是也是很有名的。

4. Boyer-Moore，這個聽說過的人應該也不會很多，這個算法在大量字元串的情況下，效率是最高的，能達到kmp的3到4倍。

上面四種算法都很重要，一般标準庫中的字元串比對都使用的是暴力法。

上面四種算法詳細的見我下面的這幾篇博文，相信你讀過後應該不會在這個問題上有什麼問題了。

《字元串比對之KMP---全力解析》

《字元串比對之---BF算法(暴力破解法)》

《字元串比對之KMP算法（續）---還原next數組》

《字元串比對之horspool算法(簡化的BM算法)》

《grep之字元串搜尋算法Boyer-Moore由淺入深（比KMP快3-5倍）》（此文為cnblog上一位美女程式猿的大作）

如果你覺得本篇對你有收獲，請幫頂。

另外，我開通了微信公衆号--分享技術之美，我會不定期的分享一些我學習的東西. 你可以搜尋公衆号： swalge  或者掃描下方二維碼關注我

（轉載文章請注明出處: http://blog.csdn.net/swagle/article/details/29201601 )