KMP

#include"stdafx.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<map>
using namespace std;

int findstr1(string a, string b)
{
    int ans = -1;
    int *next = (int*)malloc(sizeof(int)*b.size());
    memset(next, 0, sizeof(int) * b.size());
    int i = 0, j = 2;
    while (j < b.size())
    {
        if (b[i] == b[j - 1])
        {
            i++;
            if (b[j] == b[i])next[j] = next[i];
            else next[j] = i;
        }
        else
        {
            if (i != 0)
            {
                i = next[i];
                j--;
            }
        }
        j++;
    }

    i = 0; j = 0;

    while (i < a.size()&&j<b.size())
    {
        if (a[i] == b[j])
        {
            i++;
            j++;
        }
        else
        {
            if (j != 0)
                j = next[j];
            else
                i++;
        }
    }
    free(next);
    if(j==b.size())
        ans = i-j;
    return ans;
}

int main()
{
    //string a = "ABCDABE ABCDABC";
    //string b = "ABCDABC";
    //string b = "ABACABABC";
    string a = "hello";
    string b = "ABAB";

    int ans = findstr1(a, b);
    cout << ans << endl;
}