KMP字符串模式匹配算法

原理就不说了，学算法的都知道这基本上是查找一个字符串是否在另一个串中位置比较快的算法。代码如下：
[cpp]  
#include <stdio.h>  
#include <string.h>  
#define MAXSIZE 100  
int next[MAXSIZE];  
int S_lenth,D_lenth;  
char source[MAXSIZE],detination[100];  
void get_next()  
{  
    int i=1,j=0;  
    next[1]=0;  
    while(i<=D_lenth)  
    {  
        if(j==0||(detination[i-1]==detination[j-1]))  
        {  
            ++i;  
            ++j;  
            next[i]=j;  
        }  
        else  
        {  
            j=next[j];  
        }  
    }  
}  
int KMP()  
{  
    int i=0,j=1;  
    while(i<=S_lenth&&j<=D_lenth)  
    {  
        if(j==0||(source[i]==detination[j-1]))  
        {  
            ++i;  
            ++j;  
        }  
        else  
        {  
            j = next[j];  
        }  
    }  
    if(j>D_lenth)  
    {  
        return i-D_lenth;  
    }  
    else  
        return 0;  
}  
int main()  
{  
    int i=0;  
    printf("输入源串！！！\n");  
    scanf("%s",&source);  
    printf("输入模式串！！！\n");  
    scanf("%s",&detination);  
    S_lenth = strlen(source);  
    D_lenth = strlen(detination);  
    get_next();  
    printf("next数组元素为：\n");  
    for(i=1;i<=D_lenth;i++)  
    {  
        printf("%d ",next[i]);  
    }  
    printf("\n模式串开始于源串%d位置处",KMP());  
    return 0;  
}  
 
 

补充：软件开发 , C++ ,

上一个：合并有序链表
下一个：2-4动态列表