[Leetcode] Implement strStr()

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
KMPアルゴリズム!

 1 class Solution {

 2 public:

 3     void getNext(vector<int> &next, string &needle) {

 4         int i = 0, j = -1;

 5         next[i] = j;

 6         while (i != needle.length()) {

 7             while (j != -1 && needle[i] != needle[j]) j = next[j];

 8             next[++i] = ++j;

 9         }

10     }

11     int strStr(string haystack, string needle) {

12         if (haystack.empty()) return needle.empty() ? 0 : -1;

13         if (needle.empty()) return 0;

14         vector<int> next(needle.length() + 1);

15         getNext(next, needle);

16         int i = 0, j = 0;

17         while (i != haystack.length()) {

18             while (j != -1 && haystack[i] != needle[j]) j = next[j];

19             ++i; ++j;

20             if (j == needle.length()) return i - j;

21         }

22         return -1;

23     }

24 };

上は通常KMPアルゴリズムを用いているが,アルゴリズムには一定の欠陥がある.例えば,我々のパターン列pattern=「AAAAAAB」では,next配列が01230であることが容易に得られる.ターゲットマッチング列が「AAAACAAAAB」であれば、シミュレーションしてみてください.Aは何度も遡ります.すなわち,我々のnext配列最適化は徹底的ではない.最適化アルゴリズム:next[i]は、マッチング列がiでマッチングに失敗した場合に次に移動する位置を表す.以下は最適化後のnext配列を求めるコードです.2つの書き込みでnext値が異なるが,kmp関数の書き方は同じである.

 1 class Solution {

 2 public:

 3     void getNext(vector<int> &next, string &needle) {

 4         int i = 0, j = -1;

 5         next[i] = j;

 6         while (i < needle.length() - 1) {

 7             while (j != -1 && needle[i] != needle[j]) j = next[j];

 8             ++i; ++j;

 9             // ， 。 AAAAB,  4 A 0123 。

10             if (needle[i] == needle[j]) next[i] = next[j]; 

11             else next[i] = j;

12         }

13     }

14     int strStr(string haystack, string needle) {

15         if (haystack.empty()) return needle.empty() ? 0 : -1;

16         if (needle.empty()) return 0;

17         vector<int> next(needle.length() + 1);

18         getNext(next, needle);

19         int i = 0, j = 0;

20         while (i != haystack.length()) {

21             while (j != -1 && haystack[i] != needle[j]) j = next[j];

22             ++i; ++j;

23             if (j == needle.length()) return i - j;

24         }

25         return -1;

26     }

27 };

以下はKMPアルゴリズムではありませんが、コードは特に簡潔です.

 1 class Solution {

 2 public:

 3     int strStr(string haystack, string needle) {

 4         int i, j;

 5         for (i = j = 0; i < haystack.size() && j < needle.size();) {

 6             if (haystack[i] == needle[j]) {

 7                 ++i; ++j;

 8             } else {

 9                 i -= j - 1; j = 0;

10             }

11         }

12         return j != needle.size() ? -1 : i - j;

13     }

14 };