#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

int KmpFind(const char *str1, const char *str2, int next[]);
void GetNext(const char *str, int next[ ]);

int main(int argc, char *argv[])
{
    char *source = "abcdefghabcdefghhijiklm";
    char dest[20];
    int next[20];
    cin>>dest;
    GetNext(dest, next);
    cout<<endl<<KmpFind(source, dest, next);
    system("PAUSE");    
    return 0;
}

int KmpFind(const char *str1, const char *str2, int next[])
{
    int len1 = strlen(str1), len2 = strlen(str2);
    int i=0, j=0;
    if(i<j)
        return -1;
    while(i<len1 && j<len2)
    {
        if(str1[i]==str2[j] || j<0)
        {
            ++i;
            ++j;
        }
         else
              j = next[j];    
    }    
    if(j == len2)
        return i-j;
    else
        return -1;
}    
void GetNext(const char *str, int next[ ])
{
    int len = strlen(str), source = 1, dest = 0;
    next[0] = -1;
    while( source < len )
    {
        if(str[source] == str[dest] || dest<0)
        {
            ++source;
            ++dest;
            next[source] = dest;
        }    
        else
           dest = next[dest];
    }    
}    


没有经过改进的
最原始的 KMP

我在这里只说算法
至于具体的编程，楼主自己试试好了
int Index_KMP(SString S, SString T, int pos)
{
    i = pos;    j = 1;
    while(i <= S[0] && j <= T[0]) {
        if(j == 0 || S[i] == T[j]){
            i ++;        j ++;     }
        else    j = next[j];        //模式串右移
    }
    if(j > T[0])    return i - T[0]; //匹配成功
    else        return 0;        //失败    
}

//计算next的函数
void get_next(SSTring T, int &next[])
{
    j = 1;    next[1] = 0;    k = 0;
    while(j < T[0]) {
        if(k == 0 || T[j] == T[k]) {
            j ++;  k ++;  next[j] = k;
        }
        else        k = next[k];
    }
}

我现在还没学C++，因此我看不懂！！！！同样感谢你

我要的是C下的函数，同样感谢！！

我写的函数可以直接复制到 C 里面

不需要作任何修改


难道你看不出来吗
这里仅仅是使用了C++ 的输入输出
别的地方都是C的

/*此问题已经被一楼的兄弟解决！！*/
/*修改了一下第一楼的程序，在C下运行成功并得到正确结果，顶！！！*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int KmpFind(const char *str1, const char *str2, int next[]);
void GetNext(const char *str, int next[ ]);

int main()/*int argc, char *argv[])*/
{
    char *source = "abcdefghabcdefghhijiklmabc";
    char dest[20];
    int next[20],endl;
    clrscr();
    gets(dest);
    GetNext(dest, next);
    endl=KmpFind(source, dest, next);
    printf("%d",endl);
    system("PAUSE");
    return 0;
}

int KmpFind(const char *str1, const char *str2, int next[])
{
    int len1 = strlen(str1), len2 = strlen(str2);
    int i=0, j=0;
    if(i<j)
        return -1;
    while(i<len1 && j<len2)
    {
        if(str1[i]==str2[j] || j<0)
        {
            ++i;
            ++j;
        }
         else
              j = next[j];
    }
    if(j == len2)
        return i-j;
    else
        return -1;
}
void GetNext(const char *str, int next[ ])
{
    int len = strlen(str), source = 1, dest = 0;
    next[0] = -1;
    while( source < len )
    {
        if(str[source] == str[dest] || dest<0)
        {
            ++source;
            ++dest;
            next[source] = dest;
        }
        else
           dest = next[dest];
    }
}




这里是KMP的算法,那我想知道:怎么输出:NEXT函数--即那个数组呢?
希望高手给点意见!!!!!!!1
拜谢!!!!!!!!!!!!!!!!1

哥们里面不是有个GetNext()函数吗，它就是求next表用的。

串匹配还是看看 BM，TBM。 象什么 KMP 这种东西几乎不可能应用在实时性高的地方。

第1楼、第6楼代码当输入是 "hhi" 时都直接崩溃（linux 下 gcc/g++ 3.4.3 版，VC6）。而且稍一看就能发现第1楼代码中的 next[1] 永远会是初始值，比如在 main 里将 next[1] 置成某个值，运行完 GetNext() 函数后 next[1] 仍旧会是那个值，而在 KmpFind 中再用这个值你就可能死得很难看。

在
[quote]next[0] = -1;[/quote]

后面加一行

if( len>1 ) next[1]=0;

就没问题了。关于GetNext() 函数中

[quote]else dest = next[dest];[/quote]

处，老外有段相关说明很不错，供参考：

[quote]
This is the subtle part of the algorithm. The target does not begin 
t_0...t_t t_s. We could examine t_1...t_s, t_2...t_s,... successively 
to see which (if any) gives a valid prefix. But this is not necessary. 
Say the longest valid prefix is t_k...t_t t_s. Then t_k...t_t is also 
a valid prefix. But f(t) gave the length of the longest valid prefix 
of the form t_k...t_t. Thus no k such that t_k..t_t is longer than 
f(t) need be considered. Now iterate this reasoning to conclude that
only candidates t_k...t_t of lengths f(t), f(f(t)),... need be
considered.
[/quote]

附带送一个变形版本 BM 算法的演示程序

#include<stdio.h>
#include<stdlib.h>

void bm_buildtab(unsigned char *pattern,int plen,int *offtab)
{
    int i;
    for(i=0;i<256;++i) offtab[i] = plen;
    for( i=0;i<plen-1; ++i ) offtab[pattern[i]] = plen-i-1;
}

char *bm_strstr(char *source, char *pattern)
{
    static int offtab[256];
    int plen,i;
    char *end,*curend,*pend;
    if( 0==pattern[0] ) return((char *)NULL);
    if( 0==pattern[1] ) return((char *)strchr(source,pattern[0]));

    plen = strlen(pattern);
    bm_buildtab(pattern,plen,offtab);
    for( end=source; *end; ++end);
    curend = source+plen-1, pend = pattern+plen-1;
    while( curend<end )
    {
        for( ; pend>=pattern && *curend == *pend ; --curend, --pend);
        if( pend<pattern ) return(curend+1);
        curend += offtab[*curend];
        pend = pattern+plen-1;
    }

    return((char *)NULL);
}

int main()
{
    char *source ="ahrhefalalaahihkjlmn", *pattern="ahi",*get;

    printf("source: %s\npattern: %s\n",source,pattern);
    if( ( get=bm_strstr(source,pattern) ) )
        printf("get: %s\n",get);
    else printf("not get it!\n");

    return(0);
}


发现这个演示程序有个 bug，某些情况下必须对 bm_strstr 中做个调整才可能正确运行，最好不要直接抓过去用。