精华内容
下载资源
问答
  • 在两个字符串S[i]与T[j]中i可以不回溯,模式向右滑动到新比较起点k,并且k仅与模式串T有关。 令k=next[j],则: next[j]=-1(j0) next[j]=max{k|0<k<j且T0…Tk-1=Tj-k+1…Tj-1} next[j]=0(其他情况) next[j]...

    在两个字符串S[i]与T[j]中i可以不回溯,模式向右滑动到新比较起点k,并且k仅与模式串T有关。
    因此可以先看一下我之前通过看网课写的一篇KMP算法的基本解释
    令k=next[j],则:
    next[j]=-1(j==0)
    next[j]=max{k|0<k<j且T0…Tk-1=Tj-k+1…Tj-1}
    next[j]=0(其他情况)
    next[j]函数象征着模式T中最大相同前缀字串和左字串的长度。
    这里有个很好的小例子

    在这里插入图片描述
    在这里插入图片描述

    next[j]的算法分析

    在这里插入图片描述
    k=next[j-1];
    while(k!=-1)&&(t[k]!=t[j-1])
    k=next[k];
    next[j]=++k;
    next[j]的算法分析:
    k=next[j-1](由next[的定义可以知道:t0t1…tk-1=tj-k…tj-3tj-2)
    1.如果t[k]t[j-1]或k-1(不存在长度相同的前缀字串和左字串)
    则则t0t1…tk-1tk= tj-k…tj-3tj-2tj-1,因此
    next[j]=k+1,next[j]计算结束
    否则, 查找t0t1…tk的最长左子串
    k=next[k],转 1 继续执行

    在这里插入图片描述
    否则查找t0t1…tk的最长左字串
    k==next[k],转1继续执行

    在这里插入图片描述
    在这里插入图片描述
    1. 在串S和串T中分别设比较的起始下标i和j;
    2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
    2.1 如果S[i]==T[j],继续比较S和T的下一个字符;否则
    2.2 将j向右滑动到next[j]位置,即j=next[j];
    2.3 如果j=-1,则将i和j分别加1,准备下一趟比较;
    3. 如果T中所有字符均比较完毕,则返回匹配的起始下标;否则返回-1;

    展开全文
  • 从主串S的第0个字符开始和模式T的第0个字符进行比较,若相等则继续比较两者的后续字符; 否则,从主串S的第一个字符开始和模式T的第0个字符进行比较,重复上述过程,直到T中的字符全部比较完毕,则说明比较失败。 1...

    基本思想:

    从主串S的第0个字符开始和模式T的第0个字符进行比较,若相等则继续比较两者的后续字符;
    否则,从主串S的第一个字符开始和模式T的第0个字符进行比较,重复上述过程,直到T中的字符全部比较完毕,则说明比较失败。

    在这里插入图片描述
    1.在串S和串T中设比较的起始下标I和j;
    2.循环知道S或T的所有字符比较完;
    2.1如果s[i]==T[j],继续比较S和T的下一个字符;
    2.2否则,将i和j回溯(i=i-1,j=0),准备下一趟比较;
    3.如果T中所有字符均比较完,则匹配成功,返回匹配的起始比较下标(i-j);否则匹配失败,返回-1;

    代码实现如下
    在这里插入图片描述
    设串S的长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况。
    (1)最好:不成功的匹配都发生在串T的第一个字符。
    所有匹配成功的情况可能有n-m+1种
    最坏情况:不成功的匹配都发生在串T的最后一个字符。
    为什么BF算法的时间性能低?
    在每趟匹配不成功时存在大量回溯,没有利用已经部分匹配的结果。
    如何在匹配不成功的时候主串不回溯?
    主串不回溯,模式就需要向右滑动一段距离。
    因此KMP算法很好的解决这个问题

    展开全文
  • 求一个字符串在另一个字符串中的位置,称为模式匹配,如果匹配成功,则输出第一次匹配成功的位置,否则输出0。KMP算法是一种高效的模式匹配算法。要求采用KMP算法完成该题目。 输入 输入包今含若干个测试...

    描述

    求一个字符串在另一个字符串中的位置,称为模式匹配,如果匹配成功,则输出第一次匹配成功的位置,否则输出0。KMP算法是一种高效的模式匹配算法。要求采用KMP算法完成该题目。

    输入

    输入包今含若干个测试用例,每个测试用例占两行,其中第一行为目标字符串,第二行为模式串。

    输出

    对每个测试用例,用两行输出,其中第一行输出该用例的模式串的各字符的next值,第二行输出模式串在目标串中第一次匹配成功的位置。如果匹配不成功,则输出0。

    样例输入

    abcdefg
    bcd
    0000001
    0001
    110011001100
    111
    dabcabcabc
    abc

    样例输出

    0 1 1
    2
    0 1 2 3
    4
    0 1 2
    0
    0 1 1
    2
    #include<iostream>
    #include<cstring>
    using namespace std;
    string s1,s2;
    int next[50]={0};
    void Next(string s2)
    {
        int k=3,j,i;
        next[1]=0; next[2]=1;
        while(k<=s2.size()){
        j=k-1; i=next[j];
        while(j-1&&s2[j-1]!=s2[i-1]){
        j=i;
        i=next[j];
        }
        next[k]=i+1;
        k++;
        }
    }
    int Index_KMP(string s1,string s2)
    {
        int i=1,j=1;
        while(i<=s1.size()&&j<=s2.size()){
            if(s1[i-1]==s2[j-1]||j==0){i++;j++;}
            else j=next[j];
        }
        if(j>s2.size())return i-j+1;
        return 0;
    }
    int main()
    {
        int i;
        while(cin>>s1>>s2)
        {
            i=1;
            Next(s2);
            while(i<s2.size())
            {
                cout<<next[i++]<<" ";
            }
            cout<<next[i]<<endl;
            cout<<Index_KMP(s1,s2)<<endl;
        }
        return 0;
    }
    


    展开全文
  • BF 算法: #include #include #include #define MaxSize 100 //...//串的定长顺序储存结构 typedef struct// { char str[MaxSize];//储存串的一维数组 }SString; int BFIndex(SString S, int pos, SString T) {

    BF 算法:

    #include<stdio.h>
    #include<string.h> 
    #include<stdlib.h> 
    #define MaxSize 100 //串的最大长度 
    //串的定长顺序储存结构 
    typedef struct//
    {  
        char str[MaxSize];//储存串的一维数组 
    }SString;    
    int BFIndex(SString S, int pos, SString T) 
    {    
        int i = pos;   
        int j = 0; //初始化 
        while(i <=strlen(S.str)&& j<=strlen(T.str)) //两串均未达到串尾 
        {   
    	    if(S.str[i-1] == T.str[j])//继续比较后续字符 
    	    {
    	           i++;   
    			   j++;   
    		}   
    		else   //指针后退重新开始匹配 
    		{   
    		   i = i-j+1;    
    		   j = 0;  
    		}  
    	}   
    	if (j==strlen(T.str))//匹配成功 
       {      
           return (i-strlen(T.str));   
       }  
        else    //匹配失败 
    	return 0;
    }
    
    int main() 
    {  
         SString S,T;  
         int pos,ans;  
         printf("请输入主串S的字符:");  
         scanf("%s",S.str);      
         printf("请输入子串T的字符:");  
         scanf("%s",T.str);  
         printf("请输入pos的值:");  
         scanf("%d",&pos);      
         ans=BFIndex(S,pos,T);//调用BFIndex函数 
         printf("子串T在主串S中第pos个字符之后的位置为:"); 
         printf("%d\n",ans);    
         system("pause");  
         return 0;
    }
    
    


    KMP算法

    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include<string.h>
    #define MAXLEN 100//串的最大长度 
    typedef struct
    {
    	char ch[MAXLEN+1];
    }SString;
    void get_next(SString T,int next[])//求模式串next函数值 并存入数组next 
    {
    	int i,j;
    	i=1;
    	next[1]=0;
    	j=0;
    	while(i<strlen(T.ch))
    	{
    		if(j==0||T.ch[i]==T.ch[j])
    		{
    			++i;
    			++j;
    			next[i]=j;
    		}
    		else
    			j=next[j];
    	}
    }
    int Index_KMP(SString S,SString T,int pos,int next[])
    //利用模式串T的next函数求T在主串S中第pos个字符之后的位置 ,其中T非空 
    {
    	int i,j;
    	i=pos;j=1;
    	while(i<=strlen(S.ch)&&j<=strlen(S.ch))
    	{
    		if(j==0||S.ch[i]==T.ch[j])
    		{
    			++i;++j;
    		}
    		else
    	    {
    	    	j=next[j];
    		}
    	}
    	if(j>strlen(T.ch))
    		return i-strlen(T.ch);
    	else
    		return 0; 
    }
    
    int main()
    {
    	SString S,T;
    	int pos,ans,next[MAXLEN];
    	printf("请输入S串\n"); 
    	scanf("%s",S.ch);
    	printf("请输入T串\n");
    	scanf("%s",T.ch);
    	printf("请输入pos的值\n");
    	scanf("%d",&pos);
    	get_next(T,next);
    	ans=Index_KMP(S,T,pos,next);
    	if(ans==0)
    	  printf("匹配失败\n");
    	else
    	{
    		printf("模式T在主串S中第pos个字符开始第一次出现的位置为:%d\n",ans);
    	}
    }
    


    KMP扩展:

    void get_nexttval(SString T,int nextval())
    {
    	int i,j;
    	i=1;
    	nextval[1]=0;
    	j=0;
    	while(i<T.length)
    	{
    		if(j==0||T.ch[i]==T.ch[j])
    		{
    			++i;++j;
    			if(T.ch[i]!=T.ch[j])
    			  nextval[i]=j;
    			else nextval[i]=nextval[j];
    		}
    		else
    		    j=nextval[j];
    	}
    }
    
    
    



    展开全文
  • 模式匹配——BF算法 从头开始模式串对主串进行暴力比对 int BF(char S[ ], char T[ ]) { i=0; j=0; while (i<S.Length()&&j<T.length()) { if (S[i]==T[j]) { i++; j++; } ...
  • 模式匹配数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出该字串相同的所有子串,这就是模式匹配。其中原字符串成为目标串,给定的子串为模式串。通俗理解如下图1-1: 二、常用的模式...
  • 数据结构与算法实验指导 V2017 常熟理工学院 数据结构与算法实验指导与报告书 _2017-2018_学年 第_1_ 学期 专 业 物联网工程 实验名称 串与模式匹配 实验地点 N6-210 指导教师 聂盼红 计算机科学与工程学院 2017 ...
  • 数据结构模式匹配 KMP算法

    千次阅读 2019-03-13 21:23:26
    数据结构】 串 KMP算法实现 KMP算法应用于串的模式匹配中 普通模式匹配算法在进行匹配时需要频繁对主串指针进行回溯,KMP算法通过将模式向右滑动一段距离的方式避免了主串的回溯,同时降低了算法复杂度 ,由...
  • 主要介绍了C语言数据结构模式匹配字符串定位问题的相关资料,希望通过本文能帮助到大家,让大家理解这部分内容,需要的朋友可以参考下
  • 主要介绍了C语言数据结构中串的模式匹配的相关资料,需要的朋友可以参考下
  • 该文档描述了数据结构的串的相关知识,朴素的模式匹配,KMP模式匹配,相关的概念,基本知识和代码的实现
  • 模式匹配练习数据结构 数据结构 编写一段代码,将 a 设置为一个 n 个随机整数的数组,要求随机数介于 0和 n 之间。 def main(args: Array[String]): Unit = { randomArray(10).foreach(println) } def ...
  • 数据结构 串的模式匹配

    千次阅读 2020-05-05 16:58:00
    全部每周作业和视频思考题答案和解析 见浙江大学 数据结构 思考题+每周练习答案 题目一:若给定文本长度为 n,模式长度为 m,则库函数 strstr 的最坏时间复杂度是: A. O(nm) B. O(n) C. O(m) D....
  • 请问各路大神,t怎么总是0,问题出在哪: #include <stdio.h> #include <malloc.h> #define CHUNKSIZE 1 typedef struct Chunk { char ch[CHUNKSIZE]; struct Chunk *next;...}
  • while(i[0]&&j[0])//i j都不超过其串的长度 {//失配 //1:失配,当j==0时,则目标主串的检测指针前进一位,模式串检测指针回到T[1].进行下一趟的比较 //2:失配,当j>0时,那么在下一趟比较时,模式串的...
  • 数据结构 串的模式匹配算法BF、KMP

    千次阅读 2019-01-12 02:27:32
    目录 串的模式匹配 朴素的模式匹配算法(BF(BruteForce)算法) ...模式匹配数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。 假设P是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,550
精华内容 1,020
关键字:

数据结构模式匹配

数据结构 订阅