经典问题_kmp.cpp

一些ACM基本算法的测试源码

#include<iostream>
using namespace std;

#define MAXN 1000001

int next[MAXN];

void GetNext(char *p)
{   //next数组下标从1开始 
    int len = strlen(p);
    int i, j = 0;
    next[1] = 0;
    for(i = 1; i < len; i ++)
    {
        while(j > 0 && p[i] != p[j])  j = next[j];
        if(p[i] == p[j])  j ++;
        next[i + 1] = j;      
    } 
    return;    
}

int Kmp(char *t, char *p)
{
    int tlen = strlen(t);
    int plen = strlen(p);
    int i, j = 0;
    for(i = 0; i < tlen; i ++)
    {
        while(j > 0 && t[i] != p[j])  j = next[j];
        if(t[i] == p[j])  j ++;
        if(j == plen)
        {
            //printf("%d\n", i - plen + 1); 
            //return i - plen + 1;//直接返回第一次匹配成功时的初始位置(t,下标从0开始)
            j = next[j];//可以统计所有匹配地点个数    
        }      
    }   
    return -1; 
}

int main()
{
    char p[MAXN], t[MAXN];
    scanf("%s%s", p, t);
    GetNext(p);
    for(int i = 1; i <= strlen(p); i ++)
        printf("%d\n", next[i]);
    printf("%d\n", Kmp(t, p));
    system("pause");
    return 0; 
}