很久之前的KMP

KMP.cpp

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

void match_list(char * pattern, int match[] , size_t len)
{
    memset(match, 0 ,sizeof(int)*len);

    int i = 0,j = 1;
    while(j <= len)
    {
        if (pattern[j] == pattern [i])
        {
            match[j] = match[j-1] + 1;
            ++i;
        }
        else{
                i = 0;
        }
        j++;
    }
}

int main()
{
    char* pattern = "a";
    int match[strlen(pattern)];

    match_list(pattern, match, strlen(pattern));

    char* string = "jason";

    int i = 0;
    int j = 0;
    while(i <= strlen(string))
    {

        if (string[i] == pattern[j])
        {
            j++;
            if(j == strlen(pattern))
            {
                cout << i - j + 1;
                break;
            }

        }
        else{
            j = j - match[j];
        }
        ++i;
    }
    return 0;
}