[LeetCode] 028. Implement strStr() (Easy) (C++/Python)

索引：[LeetCode] Leetcode 題解索引 (C++/Java/Python/Sql)
Github: https://github.com/illuz/leetcode

028. Implement strStr() (Easy)

鏈接：

題目：https://oj.leetcode.com/problems/implement-strstr/
代碼(github)：https://github.com/illuz/leetcode

題意：

在1個字符串里找另外一個字符串在其中的位置。

分析：

這題歸在 Easy 類是由于它 O(n*n) 的暴力能過。
如果數據強點就得 Midium 以上了。

1. (C++) 這題的暴力 O(n^2) 就是兩遍 for 去找
2. (C++) 還有各種高大上的算法，比如 KMP 算法，這是經典的了，具體實現見 我的另外一篇博客。
   
3. (Python) 另外可以用 hash 去做，叫 rolling hash 算法（見 Wiki 和 StackOverflow），就是把字符串 hash 出來，按匹配串長度窗口去轉動，再去匹配。hash 字符串有很多種方法，這邊的字母好像都是小寫，有 26 個，所以就用 29 做基數（本來想像 djb2 算法用 33 做基數，可以直接 ((hash << 5) + hash) 很快，不過 int 范圍只能 hash 6 個字母而且 rolling 的時候還是要 /33，還是用 29 算了），超 int 范圍的話用 Python 就不用斟酌這個問題了。

其他還有 Boyer

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈