KMP字符串模式匹配算法实现

怼烎@ 2022-06-03 03:50 248阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h> 
    
    #define Max 100
    #define TRUE 1
    #define FALSE 0 
    
    typedef unsigned char SString[Max+1];
    
    typedef int Status;
    
    Status StrAssign(SString T,char *strs)  
    { 
        int i;  
        T[0]=0;
        for(i=0;strs[i];i++)
        {
            T[i+1]=strs[i];
            T[0]=i+1;
        }
    }  
    
    void get_next(SString T,int *next)
    {
        int i,j;
        i=1;
        j=0;
        next[1]=0;
        while(i<T[0])
        {
            if(j==0||T[i]==T[j])
            {
                ++i;
                ++j;
                next[i]=j;
            }
            else
                j=next[j];
        }
    }
    
    int Index_KMP(SString S,SString T,int pos)
    {
        int i=pos;
        int j=1;
        int next[255];
        get_next(T,next);
        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; 
    }
    
    int main()
    {
        SString S,T;
        int m;
        char strs1[Max];
        char strs2[Max];
        while(scanf("%s %s",strs1,strs2)!=EOF)
        {
            StrAssign(S,strs1);
            StrAssign(T,strs2);
            m=Index_KMP(S,T,1);
            if(m)
                printf("%d\n",m);
            else
                printf("0\n");
        }
        return 0; 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，248人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-字符串算法：KMP、模式匹配

对于字符串匹配算法中，前面介绍的算法在字符串匹配中都会有重复比较的情况，那么对于已经比较过的子串，我们是否可以用某种方法把它保存起来，等到下次要比较的时候直接跳过已经比较过的字

雨点打透心脏的1/2处/ 2023年10月04日 12:19/ 0 赞/ 10 阅读

相关 KMP字符串模式匹配算法

一简单的字符串匹配算法 1 算法思想：分别用计数指针i和j指示主串S和模式串T中当前正待比较的字符串位置。从主串S的第一个字符起，与模式串T的第一个字符比较，若

绝地灬酷狼/ 2023年03月03日 13:27/ 0 赞/ 63 阅读

相关 638-字符串模式匹配-KMP算法

KMP算法讲解1 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAL

Bertha 。/ 2022年09月12日 07:56/ 0 赞/ 201 阅读

相关 638-字符串模式匹配-KMP算法

KMP算法讲解1 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAL

小咪咪/ 2022年08月28日 12:55/ 0 赞/ 282 阅读

相关 KMP字符串模式匹配算法实现

include<stdio.h> include<stdlib.h> include<string.h> define Max 10

怼烎@/ 2022年06月03日 03:50/ 0 赞/ 249 阅读

相关字符串的模式匹配（KMP）算法

一、背景给定一个`主串`（以 S 代替）和`模式串`（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。 `Knuth-Morris-Prat

落日映苍穹つ/ 2022年05月13日 03:16/ 0 赞/ 248 阅读

相关 KMP(字符串匹配算法 c++实现)

OpenJudge: www.openjudge.cn 题目链接：[KMP][] 描述给两个字符串A、B, 从A中找出第一次出现B的位置。输入第一

- 日理万妓/ 2022年02月19日 13:47/ 0 赞/ 288 阅读

相关字符串匹配算法KMP

KMP算法的原理，这里我不写，建议参考： [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80

╰+攻爆jí腚メ/ 2022年01月14日 00:41/ 0 赞/ 448 阅读

相关『字符串模式匹配 KMP』

-------------------- 字符串模式匹配我们要先了解一下问题是什么。 > 模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中

﹏ヽ暗。殇╰゛Y/ 2021年12月21日 21:01/ 0 赞/ 260 阅读

相关 KMP算法实现字符串匹配

一需求 1 有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"。 2 现在要判断 str1 是否含

以你之姓@/ 2021年07月24日 23:06/ 0 赞/ 510 阅读