028 Implement strStr()[E]

1 題目描述

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

難度：Easy

2 題目樣例

Example 1:

Input: haystack = "hello", needle = "ll"Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"Output: -1

3 題意分析

就是實現strStr()，用C++的話來說就是std::string::find。

4 思路分析

1 偷懶

二者是完全等價的函數，況且輸入的也是string，沒有理由不偷懶（逃

代碼如下

class Solution {public: int strStr(string haystack, string needle) { return haystack.find(needle); }};

空間複雜度為 ，時間複雜度STL沒有具體要求，只是提到了最壞情況

Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case).

但這個最壞情況是顯然的，具體複雜度是多少存疑。

2 KMP

想了想，不能這麼偷懶過去了，就寫了個KMP。

KMP具體實現這裡不再總結了，思想簡單來說就是在每次失配時盡量減少模式串的回溯，同時主串指針不回溯以達到線性的時間複雜度。

代碼如下

class Solution {public: vector<int> preKMP(string& str){ int i=0; int j=-1; int len=str.size(); vector<int> next; next.resize(len+1, 0); next[0] = -1; while(i<len){ while(j!=-1 && str[i]!=str[j])j = next[j]; i++,j++; if(str[i]==str[j]) next[i]=next[j]; else next[i] = j; } return next; } int strStr(string haystack, string needle) { if(needle.empty()) return 0; vector<int> next; int i =0; int j =0; int len1 = haystack.size(); int len2 = needle.size(); next = preKMP(needle); while(i<len1){ while(j!=-1&&haystack[i]!=needle[j])j = next[j]; i++,j++; if(j>=len2) return i-j; } return -1; }};

整體時間複雜度 ，空間複雜度 ，其中m和n分別為主串和模式串的長度。

事實上這段代碼交上去的確比直接STL快了一點。

5 後記

是不是應該寫個自動機版本的試試呢（

推薦閱讀：