精华内容
下载资源
问答
  • 字符朴素模式匹配算法 方案一: //方案① int Index(String S,String T){ int i,j; int k=1; while(i<=S.length&&j<=T.length){ if(S.ch[i]==T.ch[j]){ i++; j++ } else{ i=k; ...

    字符串朴素模式匹配算法

    一、朴素模式匹配算法(简单模式匹配算法)思想:

    将主串中与模式串长度相同的子串搞出来,挨个与模式串对比
    当子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串
    若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较
    最坏时间复杂度: O(nm)
    最坏情况:每个子串的前m-1个字符都和模式串匹配,只有第m个字符不匹配
    比较好的情况:每个子串的第1个字符就与模式串不匹配

    二、代码实现

    方案一:

    //方案① 
    int Index(String S,String T){
    	int i,j;
    	int k=1;
    	while(i<=S.length&&j<=T.length){
    		if(S.ch[i]==T.ch[j]){
    			i++;
    			j++
    		}
    		else{
    			i=k;
    			j=1;
    			k++;
    		}
    	}
    	if(j>T.length){
    		return k;
    	}
    	else return 0;
    }
    

    方案二:

    //方案② 
    int Index(String S,String T){
    	int i,j;
    	while(i<=S.length&&j<=T.length){
    		if(S.ch[i]==T.ch[j]){
    			i++;
    			j++
    		}
    		else{
    			i=i-j+2;
    			j=1;
    		}
    	}
    	if(j>T.length){
    		return i-T.length;
    	}
    	else return 0;
    }
    
    展开全文
  • 模式匹配算法:简单匹配算法、KMP模式匹配 简单匹配算法 时间复杂度:O(n*m) int Index(Sstring S, int pos, Sstring T) { int i=pos, j=1; while(i<=S.len && j<=T.len) { if(S.ch[i]==T.ch...

    串的模式匹配算法:简单匹配算法、KMP模式匹配

    简单匹配算法

    时间复杂度:O(n*m)

    int Index(Sstring  S, int pos, Sstring T)
    {
    	int i=pos, j=1;
    	while(i<=S.len && j<=T.len)
    	{
    		if(S.ch[i]==T.ch[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i=i-j+2;
    			j=1;
    		}
    	}
    	if(j>=T.len)
    		return i-T.len;
    	else
    		return 0;
    }
    

    KMP模式匹配

    KMP算法
    时间复杂度:O(n+m)

    int Index_KMP(SString a, int pos, SString T)
    {
    	int i=pos, j=1;
    	while(i<=S.len && j<=T.len)
    	{
    		if(j==0 || S.ch[i]==T.ch[j])
    		{
    			i++;
    			j++;
    		}
    		else
    			j=next[j];
    	}
    	if(j>T.len)
    		return i-T.len;
    	else
    		return 0;
    }
    

    模式串的next值计算实现
    next函数值的算法:

    void Get_Next(SString T, int next[])
    {
    	int j=1, k=0;
    	next[1]=0;
    	while(j<T.len)
    	{
    		if(k==0 || T.ch[j]==T.ch[k])
    		{
    			j++;
    			k++;
    			next[j]=k;
    		}
    		else
    			k=next[k];
    	}
    }
    
    展开全文
  • 模式匹配算法

    2017-12-06 20:21:14
    模式匹配算法子串的定位操作通常称作的模式匹配,是各种处理系统中最重要的操作之一。#include #include #define MAXSTRLEN 100 int next[MAXSTRLEN]; typedef unsigned char SString[MAXSTRLEN + 1]; int ...

    串的模式匹配算法

    子串的定位操作通常称作串的模式匹配,是各种处理系统中最重要的操作之一。

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSTRLEN 100
    int next[MAXSTRLEN];
    typedef unsigned char SString[MAXSTRLEN + 1];
    int Index(SString s, SString t, int pos);
    int Index_KMP(SString s, SString t, int pos);
    void get_next(SString t, int next[]);
    void get_nextval(SString t, int nextval[]);
    void print_hyphen(int n);
    int main(void)
    {
        SString s, t;   /*s[0]和t[0]存储串的长度*/
        int i;
        printf("请输入主串的长度: ");
        scanf("%d", &s[0]);
        getchar();
        printf("请输入主串: ");
        for (i = 1; i <= s[0]; i++)
            scanf("%c", &s[i]);
        printf("请输入模式串的长度: ");
        scanf("%d", &t[0]);
        getchar();
        printf("请输入模式串: ");
        for (i = 1; i <= t[0]; i++)
            scanf("%c", &t[i]);
        int end = 0;
        int ope;
        int n;
        while (!end) {
            print_hyphen(15); printf("\n");
            printf("请输入指令来执行操作\n");
            print_hyphen(15); printf("\n");
            printf("1、简单的模式匹配算法\n2、KMP算法\n3、使用计算next函数修正值的KMP算法\n4、退出\n");
            print_hyphen(15); printf("\n");
            printf("输入要使用的功能的序号: ");
            scanf("%d", &ope);
            switch (ope) {
            case 1:
                if ((n = Index(s, t, 1)))
                    printf("模式串第一次在主串中出现的位置为:%d\n", n);
                else
                    printf("匹配失败!\n");
                break;
    
            case 2:
                get_next(t, next);
                if ((n = Index_KMP(s, t, 1)))
                    printf("模式串第一次在主串中出现的位置为:%d\n", n);
                else
                    printf("匹配失败!\n");
                break;
    
            case 3:
                get_nextval(t, next);
                if ((n = Index_KMP(s, t, 1)))
                    printf("模式串第一次在主串中出现的位置为:%d\n", n);
                else
                    printf("匹配失败!\n");
                break;
    
            case 4:
                printf("再见!\n");
                end = 1;
                break;
    
            default:
                printf("无此序号,请重新输入!\n");
            }
        }
        return 0;
    }
    int Index(SString s, SString t, int pos)
    {
        int i, j;
        i = pos;
        j = 1;
        while (i <= s[0] && j <= t[0]) {
            if (s[i] == t[j]) {
                ++i;
                ++j;
            }
            else {
                i = i - j + 2;
                j = 1;
            }
        }
        if (j > t[0])
            return i - t[0];
        else
            return 0;
    }
    int Index_KMP(SString s, SString t, int pos)
    {
        int i, j;
        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;
    }
    void get_next(SString t, int next[])
    {
        int 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];
        }
    }
    void get_nextval(SString t, int nextval[])
    {
        int i = 1, j = 0;
        nextval[1] = 0;
        while (i < t[0]) {
            if (j == 0 || t[i] == t[j]) {
                ++i;
                ++j;
                if (t[i] != t[j])
                    nextval[i] = j;
                else
                    nextval[i] = nextval[j];
            }
            else
                j = nextval[j];
        }
    }
    void print_hyphen(int n)
    {
        while (n--)
            printf("-");
    }
    
    展开全文
  •   的模式匹配即子串定位是一种重要的运算。设s和t是给定的两个,在...简单模式匹配算法 KMP算法 简单模式匹配算法:   算法思想:首先将s1与t1进行比较,若不同,就将s2与t1进行比较,…,直到si和t1...

      串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,在主串s中找到等于子串t的过程称为模式匹配,如果找到,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回-1。t也称为模式。

    串的模式匹配有两种算法:
    • 简单的模式匹配算法
    • KMP算法

    简单的模式匹配算法:
      算法思想:首先将s1与t1进行比较,若不同,就将s2与t1进行比较,…,直到si和t1相同,再将它们之后的字符进行比较,若也相同,则如此继续往下比较,当si与tj不同时,则s返回到本趟开始字符的下一个字符,即si-j+2,t返回到t1,继续开始下一趟的比较,重复上述过程。若t中的字符全部比完,则说明本趟匹配成功,本趟的起始位置是i-j+1或i-t[0],否则,匹配失败。
      该算法比较简单,算法代码这里就不再给出。
    KMP算法
      算法思想:算法中引入一个next数组:
    next[j]={0,j=1Max1, next[j]=\left\{ \begin{aligned} 0,当j = 1时 \\ Max \\ 1,其他情况 \end{aligned} \right.
      其中:Max的取值为:
    Max={k1&lt;k&lt;jp1p2...pk1=pjk+1...pj1 Max=\left\{ \begin{aligned} k|1&lt;k&lt;j且&#x27;p_1p_2...p_{k-1}=&#x27;&#x27;p_{j-k+1}...p_{j-1}&#x27; \end{aligned} \right.
    例如:

    next[j]的计算过程如下:

    • j=1时,根据定义next[1]=0;
    • j=2时,由于不存在这样的正整数k使得1<k<2,所以属于其他情况,此时next[2]=1;
    • j=3时1<k<3,此时k只能取2,比较p1与p2(即pj-k+1或者说是pj-1),发现a!=b,所以属于其他情况,next[3]=1;
    • j=4时1<k<4,此时k可以取2、3两个:首先k取2,则比较p1与p3(即pj-k+1或者说是pj-1),发现相等,说明k可以取2;然后计算k取3时的情况,需要判断p1p2与p2p3(即pj-k+1pj-1),发现ab!=ba,k不可以取3;最后找出k的最大取值为2,所以next[4]=2
    • j=5时1<k<5,此时k可以取2、3、4三个 :首先k取2,则比较p1与p4(即pj-k+1或者说是pj-1),发现相等,说明k可以取2;然后计算k取3时的情况,需要判断p1p2与p3p4(即pj-k+1pj-1),发现ab!=aa,k不可以取3;然后计算k取4时的情况,需要判断p1p2p3与p2p3p4(即pj-k+1pj-k+2pj-1),发现aba!=baa,k不可以取4;最后找出k的最大取值为2,所以next[5]=2
    • j=6时1<k<6,此时k可以取2、3、4、5四个:首先k取2,则比较p1与p5,发现由于a!=b,说明k不可以取2;然后计算k取3时的情况,需要判断p1p2与p4p5,发现ab==ab,k可以取3;然后计算k取4时的情况,需要判断p1p2p3与p3p4p5,发现aba!=aab,k不可以取4;然后计算k取5时的情况,需要判断p1p2p3p4与p2p3p4p5,发现abaa!=baab,k不可以取5;最后找出k的最大取值为3,所以next[6]=3
    • j=7时,同理照此方法取k=2、3、4、5、6进行比较,最后计算出没有一个k值满足,所以属于其他情况,因而next[7]=1
    • j=8时,按照上述方式进行计算k=2、3、4、5、6、7比较后,发现只有k只能取2,因而next[8]=2。

    从而得出next数组中的值

    算法代码如下:

    #include "stdafx.h"
    #include <stdio.h>
    
    //查找满足条件的最大的k值,tr为模式串,l为当前比较的位置
    int Max_k(char t[],int l)
    {
    	int i = 0;
    	int max = 0;
    	int k = 0;
    	bool bIsEqual = true;
    	for(k = 2;k < l;k++)
    	{
    		bIsEqual = true;
    		for(i = 1;i <k;i++)
    		{
    			if(t[i] != t[l-k+i])
    				bIsEqual = false;//不满足'p1p2...p(i-1)==p(l-k+1)...p(l-1)'条件
    		}
    		if(bIsEqual)
    			max = k;
    	}
    	return max;
    }
    //计算模式串的next[j]数组
    void NextArr(int next[],int t_len,char t[])
    {
    	next[1] = 0;//netx[1]=0
    	next[2] = 1;//1<k<i,此时i = 2,为其他情况,所以next[2] = 1
    	int i = 3;
    	int max = 0;
    	for(i = 3;i < t_len;i++)
    	{
    		max = Max_k(t,i);
    		if(0 == max)
    			next[i] = 1;//其他情况
    		else
    			next[i] = max;
    	}
    }
    //找到匹配的主串开始位置
    //s:主串,t:子串,s_len:主串长度,t_len:子串长度,pos:从主串的pos位置处开始查找,next:不匹配时j的重新定位位置
    int KMP_Pos(char s[],char t[],int s_len,int t_len,int pos,int next[])
    {
    	int i = pos;
    	int j = 1;
    	while(i < s_len && j < t_len)
    	{
    		if(j == 0 || s[i] == t[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    	if(j >= t_len)
    		return i - t_len + 1;
    	else
    		return 0;
    }
    
    int main(int argc, char* argv[])
    {
    	char s[] = {'0','a','b','a','b','c','a','b','c','a','c','b','a','b'};//主串
    	int s_len = 14;
    	char t[] = {'0','a','b','c','a','c'};//模式串
    	int t_len = 6;
    	int next[6];
    	NextArr(next,t_len,t);
    	int pos = KMP_Pos(s,t,s_len,t_len,1,next);
    	printf("主串匹配模式串的第一个位置为:%d\n",pos);
    	return 0;
    }
    
    

    运行结果为:
    在这里插入图片描述
      KMP算法的难点就在于计算next数组,当计算出模式串的next的数组后,再去进行模式串匹配算法就比较简单了。

    展开全文
  •  这个算法理解起来有点难受,建议看下简单串模式匹配算法 BF算法 刷下经验,如上链接。 2.优化匹配算法:  相比于Brute-Force(BF算法),每当一趟匹配出现字符不等时,不需要回溯i指针(目标指针),并且...
  • 数据结构 模式匹配算法BF、KMP

    千次阅读 2019-01-12 02:27:32
    朴素的模式匹配算法(BF(BruteForce)算法) BF的算法实现 算法分析 KMP模式匹配算法 字符前缀后缀 最长公共前后缀 next数组 kmp算法实现 KMP算法的改进 ​nextval数组实现 的模式匹配 模式匹配是数据...
  • 文章目录串串的定义的存储结构的顺序存储的链式存储结构模式匹配算法——BF算法 的定义 的逻辑结构和线性表极为相似,区别仅在于的数据对象约束为字符集。然而,的基本操作和线性表有很大差别...
  • 字符模式匹配有着广泛的应用,如求...目标T :“Beijing”模式 P :“jin”匹配结果= 3一、BF算法(也叫传统的字符串模式匹配算法、朴素模式匹配、穷举模式匹配)BF(Bruce Force)算法是普通的模式匹配算法,BF算法的...
  • 数据结构——模式匹配算法

    千次阅读 2017-05-10 18:11:09
    2、模式匹配算法  的查找操作也称作的模式匹配操作,模式匹配操作的具体含义是:在主(也称作目标)中,从位置start开始查找是否存在子串(也称作模式),如在主中查找到一个与模式相同的子串,...
  • 一、对一个中的某子串的定位操作称为 模式匹配; 二、模式:待定位的子串 三、基本思想:从主中的第一个位置起和模式的第一个字符开始比较 如果相等,则继续比较后续字符;...//简单模式匹配...
  • 本文主要讲解的经典模式匹配算法—Brute-Force。 1 基本思想 的模式匹配也称为子串的定位操作。设有主S和子串T,如果在主S中找到一个与子串T相等的子串,则返回T的第一个字符在S中的位置。其中S称为...
  • 模式匹配算法(KMP算法,BF算法+算法详解+实现代码) 子串的定位操作是找子串在主中从第pos个字符后首次出现的位置,又被称为的模式匹配 一、BF模式匹配算法 BF算法思想:Brute-Force算法又称蛮力匹配算法...
  • 算法案例分析—字符串模式匹配算法

    千次阅读 多人点赞 2020-09-09 19:49:13
    今天来和大家分享一个关于字符比较的模式匹配算法,在数据结构中对字符的相关操作中,对子串的定位操作通常称为的模式匹配,同样他也是各种处理中最重要的操作之一,同时子串也称为模式,关于主和模式...
  • KMP模式匹配算法:(就是一种在一个字符中定位另一个的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法,可以证明它的时间复杂度为O(m+n)。) 具体方法为:若主为S[m],子串为T[n],当第一次搜索到...
  • 简单模式匹配算法 代码 没几行 #include <iostream> using namespace std; typedef struct { char data[50];//存放字符 int length;//存放长 }SqString;//顺序类型 void StrAssign(SqString &...
  • 文章目录前言一、简单模式匹配算法1.算法思想2.简单模式匹配算法代码3.测试结果一、KMP算法1.算法思想2.简单模式匹配算法代码3.测试结果 前言 本文主要讲述的三种模式匹配算法(主和模式中字符都存放在下标1-...
  • 一个字符匹配算法,最简单的匹配和常用的KMP匹配算法,刚刚研究明白,原理大家自己在网上搜一下吧,代码跟大家分享一下。
  • 朴素模式匹配算法的基本思想: 对主的每一个字符作为子串开头,与模式进行匹配。对主做大循环,每个字符开头做模式长度的小循环,直到匹配成功或全部遍历完成为止。 代码实现非常简单: int ...
  • 模式匹配是最重要和最复杂的一个操作,其实也就是的查找,其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的模式匹配算法。   模式匹配操作的具体含义是:   在主(也称做目标)S中,...
  • 依次类推,直至模式T中的每个字符依次和主S中的一个连续的字符序列相等,则称匹配成功,函数值为和模式T中的每个字符依次和主S中的序号,否则称匹配不成功,函数值为0,分别利用计数指针i和j指示主S和模式串T...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,671
精华内容 32,668
关键字:

串的简单模式匹配算法