Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
這里需要注意的是不需要把母字符串全部迭代一次，只需要到還剩下子串長(zhǎng)度的索引地方。 代碼一：
class Solution {public: int strStr(string haystack, string needle) { int h_len = haystack.length(); int n_len = needle.length(); int rel = -1; if(h_len < n_len) return rel; if(haystack == needle || needle == "") return 0; for(int i = 0; i <= h_len - n_len; i++) { for(int k = 0, j = i; k < n_len && j < h_len; k++, j++) { if(haystack[j] != needle[k]) break; else if(k == n_len - 1) return i; } } return rel; }};代碼二：把上面的代碼精簡(jiǎn)一下。
class Solution {public: int strStr(string haystack, string needle) { int m = haystack.length(), n = needle.length(); if (!n) return 0; for (int i = 0; i < m - n + 1; i++) { int j = 0; for (; j < n; j++) if (haystack[i + j] != needle[j]) break; if (j == n) return i; } return -1; }};當(dāng)然在尋找子串方面，KMP是最經(jīng)典的算法。 使用KMP尋找子串可以得到：
class Solution {public: int strStr(string haystack, string needle) { int m = haystack.length(), n = needle.length(); if (!n) return 0; vector<int> lps = kmpPRocess(needle); for (int i = 0, j = 0; i < m; ) { if (haystack[i] == needle[j]) { i++; j++; } if (j == n) return i - j; if (i < m && haystack[i] != needle[j]) { if (j) j = lps[j - 1]; else i++; } } return -1; }private: vector<int> kmpProcess(string& needle) { int n = needle.length(); vector<int> lps(n, 0); for (int i = 1, len = 0; i < n; ) { if (needle[i] == needle[len]) lps[i++] = ++len; else if (len) len = lps[len - 1]; else lps[i++] = 0; } return lps; }};KMP算法的介紹：
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-Words/ http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/ BOOK: Introduction to Algorithm
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
