KMP

#include <iostream>
#include <vector>
using namespace std;
vector<int> kmpTable(string& pattern) {
    int len = pattern.length(), j = 0;
    vector<int> table(len, 0);
    for(int i = 1; i < len; i++) {
        while(j && pattern[i] != pattern[j])
            j = table[j-1];
        if(pattern[i] == pattern[j])
            table[i] = ++j;
    }
    return table;
}

vector<int> kmp(string& context, string& pattern) {
    vector<int> result;
    auto table = kmpTable(pattern);
    int n = context.size(), m = pattern.size(), j = 0;
    for(int i = 0; i < n; i++) {
        while (j && context[i] != pattern[j])
            j = table[j - 1];
        if (!(context[i] ^ pattern[j]))
            if(j == m-1) {
                result.push_back(i - m + 1);
                j = table[j];
            }  else
                j++;
    }
    return result;
}

void searchString(string& context, string& pattern) {
    vector<int> searchPos = kmp(context, pattern);
    for(int sPos : searchPos) {
        cout<<context.substr(sPos, pattern.length())<<endl;
    }
}

int main(int argc, char** argv){
    string context = "ABC ABCD ABCDEF";
    string pattern = "ABCD";
    searchString(context, pattern);
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}