開源地址：https://github.com/jiauzhang/algorithms
題目描述
* https://leetcode-cn.com/problems/implement-strstr
* 給定一個 haystack 字串和一個 needle 字串，
* 在 haystack 字串中找出 needle 字串出現的第一個位置(從0開始)，
* 如果不存在，則回傳 -1，
*
* 示例 1:
* 輸入: haystack = "hello", needle = "ll"
* 輸出: 2
*
* 示例 2:
* 輸入: haystack = "aaaaa", needle = "bba"
* 輸出: -1
*
* 說明:
* 當 needle 是空字串時，我們應當回傳 1.
解題思路
- 最簡單的方法就是暴力匹配了，這里不做敘述了
- 經典的解法就是 KMP 演算法進行匹配，KMP 演算法的核心部分
是計算最大公共前后綴，產生 next 陣列
換一種思路理解這個陣列，該陣列其實是指示模板字串中
擁有的最大相同子字串模板，這樣就可以直接跳過那些不存在
相同模板的子字串，從而加速模板遷移的速度，而不需要像
暴力匹配法那樣，每一次失敗都需要重頭開始匹配，這就是
KMP 演算法速度比較快的原因，其演算法復雜度為 O(M+N) - 還一些與 KMP 演算法類似的，比如 BM 演算法、Sunday 演算法等
示例代碼
class Solution {
public:
int strStr(string haystack, string needle) {
if (!needle.size())
return 0;
if (!haystack.size())
return -1;
vector<int> next;
get_next(needle, next);
int i = 0, j = 0;
/*
這里要格外注意，除錯了很久才找到錯誤原因
必須對 string::size() 函式的回傳值進行強制型別轉換
*/
while (i < (int)haystack.size() && j < (int)needle.size()) {
if ((j == -1) || (haystack[i] == needle[j])) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == needle.size()) {
return i - j;
} else {
return -1;
}
}
void get_next(string &tmpl, vector<int> &next) {
next.resize(tmpl.size());
next[0] = -1;
int k = -1;
int j = 0;
while (j < next.size() - 1)
{
if (k == -1 || tmpl[j] == tmpl[k])
{
k++;
j++;
if (tmpl[j] != tmpl[k])
next[j] = k;
else
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10535.html
標籤：其他
下一篇：全國大陸電話區號以及號碼分布