KMP算法

KMP算法==源代码

#include
using namespace std;

/**
*KMP-Table
*input: pattern
*output : overlap[]
*/
void kmp_table(const char * P, int * overlap)
{
    overlap[0] = -1;
    overlap[1] = 0;
    unsigned int j = 2;
    int cnd = 0;

    while(j < strlen(P))
    {
        if( P[j-1] == P[cnd])
        {
            overlap[j] = cnd + 1;
            ++j;
            ++cnd;
        }
        else if( cnd > 0)
            cnd = overlap[cnd];
        else
        {
            overlap[j] = 0;
            ++j;
        }
    }
}

/**
*KMP_Search
*input: char * Target ;  char * Pattern:
*output ; the position of the Pattern in Traget;
**/
int kmp_search(const char * T, const char * P)
{
    int n = strlen(T);
    int m = strlen(P);
    int * overlap = new int[m];
    int j = 0;

    kmp_table(P,overlap);

    for( int k = 0; k < m; k++)
    {
        cout<    }
    cout<
    for( int i = 0; i < n; i++)
    {
        for(;;)
        {
            if( T[i] == P[j])
            {
                j++;
                if(j == m)
                    return i-m + 1  ;
                break;
            }
            else if(j == 0) break;
            else
            {
                j = overlap[j];
            }
        }
    }
    return -1;
}

int main()
{
    char * S = "acabaabaabcacaabc";
    char * W = "abaabcac";

    int p = kmp_search(S,W);

    cout<<"p = "<< p <}