Knuth–Morris.cpp

int main() {
    
    string what,where;
    cin >> what >> where;
    
    int ret = 0, whatLen = what.length(), whereLen = where.length();
    
    vector<int> res(whatLen);
    res[0] = 0;
    
    for (int k = 0, i = 1; i < whatLen; i++){
        while(k > 0 && what[i] != what[k])
            k = res[k-1];
        
        if (what[i] == what[k])
            k++;
        
        res[i] = k;
    }
    
    for (int k = 0, i = 0; i < whereLen; ++i){
        while ((k>0) && (what[k] != where[i]))
            k = res[k-1];
        
        if (what[k] == where[i])
            k++;
        
        if (k == whatLen)
            ret += (i- whatLen +1);
    }
    
    std::cout << ret;
}