【毎日1題】LeetCode 0028.文字列の一致

オープンソースアドレス: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)

である.

は、BMアルゴリズム、Sundayアルゴリズムなどの

のようなKMPアルゴリズムと同様のものもある.
サンプルコード

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (!needle.size())
            return 0;
        
        if (!haystack.size())
            return -1;
        
        vector 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 &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];
            }
        }
    }
};