公里周日

模式匹配算法c++实现

class Solution {
    //sunday
public:
    int strStr(string haystack, string needle) {
    
        int n = haystack.size(), m = needle.size();

        unordered_map<char,int> shift;
        for(int i = 0; i < m; ++i){
    
            shift[needle[i]] = m - i;//How much computing in each character need to shift
        }
        
        int idx = 0,i = 0;
        while(idx < n){
    
            for(i = 0; i < m; ++i){
    
                if(haystack[idx+i] != needle[i]){
    
                    break;
                }
            }

            if(i == m) return idx;//匹配成功
            if(idx+m>n) return -1;//防止越界
            if(shift[haystack[idx+m]]){
    //A term in the range before can move parts
                idx += shift[haystack[idx+m]];
            }else{
    //After a is not within the scope of Give up the area directly
                idx += m+1;
            }
        }
        return -1;
    }
};

class Solution {
    //kmp
public:
    int strStr(string haystack, string needle) {
    
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
    
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
    
            while (j > 0 && needle[i] != needle[j]) {
    
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
    
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
    
            while (j > 0 && haystack[i] != needle[j]) {
    
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
    
                j++;
            }
            if (j == m) {
    
                return i - m + 1;
            }
        }
        return -1;
    }
};

class Solution {
    //kmp
public:
void nextT(string &t, vector<int> &next,int n)
{
    
    int j = 0, k = -1;
    next[0] = -1;
    while(j < n-1) {
    
        if(k == -1 || t[j] == t[k]) {
    
            next[++j] = ++k;
        } else {
    
            k = next[k];
        }
    }
}
int KMP(string &s, string &t)
{
    
    int m = s.size();
    int n = t.size();
    int i = 0, j = 0;
    vector<int> next(n);
    nextT(t,next,n);

    while(i < m && j < n) {
    
        if(j == -1 || s[i] == t[j]) {
    
            ++i;
            ++j;
        } else {
    
            j = next[j];
        }
    }
    if(j == n)
        return i - j;
    return -1;
}

int strStr(string haystack, string needle)
{
    
    return KMP(haystack,needle);
}
};

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