KMP Algorithm

#include<bits/stdc++.h>
#define ll long long

// return a vector, which contains all indexes that pattern is found in base
template <typename T> vector<int> KMP (T &base, int base_size, T &pattern, int pattern_size) {
    
    vector<int> kmp; // vector contains all position i that pattern can be found in base
    int *lps = new int[pattern_size];
    
    // pre-process to fill lps
    int past_len = 0;
    lps[0] = 0;
    for (int i = 1; i < pattern_size;) {
        if (pattern[i] == pattern[past_len]) {
            lps[i] = past_len+1;
            i++; past_len++;
        }
        else {
            if (past_len > 0) {
                past_len = lps[past_len-1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    // search for pattern in base
    for (int i = 0, j = 0; i < base_size;) {
        while(i < base_size && j < pattern_size && base[i] == pattern[j]) 
            i++, j++;
        
        if (j == pattern_size) {
            kmp.push_back(i-pattern_size);
            j = lps[j-1];
            continue;
        }
        
        if (i == base_size)
            break;
        
        if (j != 0)
            j = lps[j-1];
        else
            i++;
        
    }
        
    return kmp;
    
}