题解 | #Zero-complexity Transposition#

/*
描述
字符串匹配
输入描述：
For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.
输出描述：
You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.
*/

#include<iostream>
#include<string>
#include<vector>

using namespace std;


vector<int> getNext(string pattern) {
    vector<int> arr;
    arr.push_back(0);
    int x = 1, now = 0;
    while (x < pattern.size()) {
        if (pattern[now] == pattern[x]) {
            now++;
            x++;
            arr.push_back(now);
        }
        else if (now > 0) {
            now = arr[now - 1];
        }
        else {
            x++;
            arr.push_back(0);
        }
    }
    return arr;
}


int countMatch(string text, string pattern, vector<int> arr_next) {
    int n = text.size(), m = pattern.size();
    int count = 0;
    int i=0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        else if (j>0){
            j = arr_next[j - 1];
        }
        else {
            // j = 0 in this case, move the text pointer one step right.
            i++;
        }
        if (j == m) {
            // match
            count++;        
            j = arr_next[j - 1];
        }
    }
    return count;
}


int BruceForce(string text, string pattern, int count=0) {
    int n = text.size();
    int m = pattern.size();
    for (int i = 0; i <= n - m; ++i)
        if (text.substr(i, m) == pattern)
            count++;

    return count;
}



int main() {
    string pattern, text;
    cin >> text >> pattern;
    int count = 0;

    // method1: KMP algotithm
    vector<int> arr_next;
    arr_next = getNext(pattern);
    count = countMatch(text, pattern, arr_next);

    // method 2 : Bruce force
    //count = BruceForce(text, pattern);

    cout << count << endl;
    return 0;
}