#LeetCode:28. Implement strStr()

雖然本來應該用簡單的字串比對就可以解了,但想想字串比對可以用個 KMP/MP 演算法來解,所以就順便練一下了,詳細解說可見演算法筆記

C++(4ms)

/*******************************************************/
/* LeetCode 28. Implement strStr()                     */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/23                                 */
/*******************************************************/
class Solution {
public:
  int strStr(string haystack, string needle) {
    if(needle == "") return 0;
    if(haystack.length() < needle.length()) return -1;

    // Build failure
    vector<int> failure(needle.length());
    for(int i = 1, j = failure[0] = -1 ; i < needle.length() ; ++i){
      while(j >= 0 && needle[j+1] != needle[i]) j = failure[j];
      if(needle[j+1] == needle[i]) ++j;
      failure[i] = j;
    }

    // Search
    for(int i = 0, j = -1 ; i < haystack.length() ; ++i){
      while(j >= 0 && haystack[i] != needle[j+1]) j = failure[j];
      if(haystack[i] == needle[j+1]) ++j;

      if(j == needle.length() - 1){
        return i - needle.length() + 1;
      }
    }

    return -1;
  }
};
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: