#字符串 #实现strStr

implement-strstr.cpp

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack.size() < needle.size())
            return -1;
        if (needle.size() == 0)
            return 0;
        for (int i = 0; i < haystack.size() - needle.size() + 1; ++i) {
            if (haystack[i] == needle[0]) {
                int k = 0;
                for (; k < needle.size(); ++k) {
                    if (haystack[i+k] != needle[k])
                        break;
                }
                if (k == needle.size())
                    return i;
            }
        }
        return -1;
    }
};

// ***************************** KMP ***************************** //
class Solution {
public:

  	// Partial Match Table 部分匹配表
    void get_pmt(const string& patten, int* pmt) {
        // case1: 先if 后while
        //     a a b a a  a c
        //     0 1 2 3 4  5 6
        // j   0 1 0 1 2 (1) 0
        // pmt 0 1 0 1 2 (1) 0
        // i   1 2 3 4 5  6  7

        // case1: 先while 后if
        //     a a b a a  a c
        //     0 1 2 3 4  5 6
        // j   0 1 0 1 2 (2) 0
        // pmt 0 1 0 1 2 (2) 0
        // i   1 2 3 4 5  6  7
        pmt[0] = 0;
        int j = 0;
        for (int i = 1; i < patten.size(); ++i) {
            // aabaaac         aabaaaac      i++
            //       |     =>   |        => 
            //     aabaaac     aabaaac       j++
            while (patten[i] != patten[j] && j > 0) {
                j = pmt[j - 1];
            }
            if (patten[i] == patten[j]) {
                j++;
            }  
            pmt[i] = j;
        }
    }

    int kmp(const string& s, const string& patten, int* pmt) {
        int j = 0;
        for (int i = 0; i < s.size(); ++i) {
            while (s[i] != patten[j] && j > 0) {
                j = pmt[j - 1];
            }
            if (s[i] == patten[j]) {
                j++;
            }
            if (j == patten.size())
                return i - j + 1;
        }
        return -1;
    }

    int strStr(string haystack, string needle) {
        if (haystack.size() < needle.size())
            return -1;
        if (needle.size() == 0)
            return 0;
        
        int pmt[needle.size()];
        get_pmt(needle, pmt);
        return kmp(haystack, needle, pmt);
    }
};