#include <iostream>
#include <string>
using namespace std;
int b_force_match(string str, string ptr)
{
    int i, j, temc;
    int tlen = ptr.length();
    int plen = str.length();
    for (i = 0, j = 0; i <= plen - tlen; i++)
    {
        temc = i;
        j = 0;
        while (str[temc] == ptr[j] && j < tlen)
        {
            temc++;
            j++;
        }
        if (j == tlen)
            return i;
    }
    return -1;
}
void clnext(string str, int *next)
{
    int len=str.length();
    next[0] = -1;
    int k = -1;
    for (int q = 1; q < len; q++)
    {
        while (k > -1 && str[k + 1] != str[q])
            k = next[k];//回溯
        if (str[k + 1] == str[q])
           k++;
        next[q] = k;
    }
}
int KMP(string str,string ptr)
{
    int slen=str.length();
    int plen=ptr.length();
    int *next = new int[plen];
    clnext(ptr, next);
    int k = -1;
    for (int i = 0; i < slen; i++)
    {
        while (k >-1&& ptr[k + 1] != str[i])
            k = next[k];
        if (ptr[k + 1] == str[i])
            k = k + 1;
        if (k == plen-1)
        {
            delete next;
            return i-plen+1;
        }
    }
    delete next;
    return -1;
}
int main()
{
    string str = "ahraaahahafafderqhgadgdfghadfhnmym,,aryzkiababaabaftyacfabaou";
    string ptr = "ababaabaf";
    cout << "patternmatch" << endl;
    cout << "b_force:" << endl;
    cout << b_force_match(str, ptr) << endl;
    cout<<"KMP:"<<endl;
    cout << KMP(str, ptr) << endl;
    return 0;
}