【数据结构】KMP算法（c语言）

男娘i 2024-04-17 20:47 78阅读 0赞

#include <stdio.h>
    #include <string.h> 
    #include <stdlib.h>
     
    typedef int Position;	//返回数组下标
    #define NotFound -1		
     
    void BuildMatch( char *pattern, int *match )
    {
        Position i, j;
        int m = strlen(pattern);
        match[0] = -1;				//match[0]肯定是-1
         
        for ( j=1; j<m; j++ ) {		//对每一个下标计算match值
            i = match[j-1];			//把前一个match值记在i里
            while ( (i>=0) && (pattern[i+1]!=pattern[j]) )
                i = match[i];		//让i回退
            if ( pattern[i+1]==pattern[j] )
                 match[j] = i+1;
            else match[j] = -1;
        }
    }
     
    Position KMP( char *string, char *pattern )
    {
        int n = strlen(string);		//得到字符串长度
        int m = strlen(pattern);	//得到模式串长度
        Position s, p, *match;
         
        if ( n < m ) return NotFound;
        match = (Position *)malloc(sizeof(Position) * m);	//定义整型数组match
        BuildMatch(pattern, match);			//计算match的值
        s = p = 0;							//一开始指向起点0
        while ( s<n && p<m ) {				//s和p都还没到结尾
            if ( string[s]==pattern[p] ) {
                s++; p++;					//相配则一起往前移动
            }
            else if (p>0) p = match[p-1]+1;	//不相配，p指针往回移
            else s++;						//p=0，第一个字符就不匹配，s指针往前移
        }
        return ( p==m )? (s-m) : NotFound;	//p到结尾，匹配成功，返回匹配上的位置s-m。否则匹配失败
    }
     
    int main()
    {
        char string[] = "This is a simple example.";
        char pattern[] = "simple";
        Position p = KMP(string, pattern);
        if (p==NotFound) printf("Not Found.\n");
        else printf("%s\n", string+p);
        return 0;  
    }

代码来自[中国大学MOOC][MOOC]浙江大学版数据结构

[MOOC]: https://www.icourse163.org/