精华内容
下载资源
问答
  • 基于字符串模式匹配算法的病毒感染检测问题(KMP算法)
    千次阅读
    2021-11-15 22:38:21

    头文件(tou.h):

    void get_next(char T[], int next[]);
    
    int Index_KMP(char S[], char T[]);
    
    void move1(char a[]);
    
    void transform(char a[]);
    
    void Judge(char S[], char T[]);
    
    void gcd(char a[]);

    头文件中函数的实现(tou.cpp):

    #define _CRT_SECURE_NO_WARNINGS  
    #include<stdio.h>
    #include<string.h>
    #include"tou.h"
    
    void move1(char a[]) {      //将数组a整体向后移动一位,让a[0]失效
    	for (int i = strlen(a); i > 0; i--) {
    		a[i] = a[i - 1];
    	}
    }
    
    void transform(char a[]) {  //将数组头(a[1])调到数组尾,数组整体向前进一位
    	int length = strlen(a)-1;
    	char head = a[1];
    	for (int i = 1; i < length; i++) {
    		a[i] = a[i + 1];
    	}
    	a[length] = head;
    }
    
    void gcd(char a[]) {       //颠倒数组元素的顺序(数组下标从1开始)
    	int length = strlen(a) - 1;
    	for (int i = 1; i < 1 + length / 2; i++) {
    		char temp = a[i];
    		a[i] = a[length + 1 - i];
    		a[length + 1 - i] = temp;
    	}
    }
    
    void get_next(char T[], int next[]) {    //根据模式串设置好next[]数组中对应的值
    	int length_T = strlen(T)-1;
    	int i = 1, j = 0;
    	next[1] = 0;
    	while (i < length_T) {
    		if (j == 0 || T[i] == T[j]) {
    			i++, j++;
    			next[i] = j;
    		}
    		else
    			j = next[j];
    	}
    }
    
    int Index_KMP(char S[], char T[]) {    //KMP算法。在主串S中找 是否有与模式串T相等的串
    	int next[100] = {};
    	get_next(T, next);     
    
    	int length_S = strlen(S)-1;
    	int length_T = strlen(T)-1;
    	int i = 1, j = 1;
    
    	while (i <= length_S && j <= length_T) {
    		if (j == 0 || S[i] == T[j]) {
    			i++, j++;
    		}
    		else j = next[j];
    	}
    	if (j > length_T) return 1;
    	else return 0;
    }
    
    void Judge(char S[], char T[]) {      //判断人DNA是否感染环状病毒DNA
    	int length_T = strlen(T) - 1;
    	int i = length_T;
    	while (i) {
    		transform(T);
    		if(Index_KMP(S,T)) break;
    		gcd(T);                       //颠倒模式串重新判断
    		if (Index_KMP(S, T)) break; 
    		gcd(T);                       //恢复模式串
    		i--;
    	}
    	if (i) printf("是否感染:YES");
    	else printf("是否感染:NO");
    }

    主函数(ceshi1.cpp):

    #define _CRT_SECURE_NO_WARNINGS   
    #include<stdio.h>
    #include<string.h>
    #include"tou.h"
    
    int main() {
    	while (1) {
    		char T[100] = {};     //模式串(病毒DNA)
    		char S[100] = {};     //主串(人DNA)
    
    		printf("请输入 病毒的DNA序列 和 人的DNA序列:\n");
    		scanf("%s%s", T, S);
    
    		if (T[0] == '0' && S[0] == '0') break;   //结束条件
    
    		move1(S), move1(T);
    
    		Judge(S, T);
    		printf("\n\n");
    	}
    	return 0;
    }

    测试结果:

    更多相关内容
  • 《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
  • 关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
  • 数据结构之字符串模式匹配

    千次阅读 2018-05-18 22:44:09
    1.引入 字符串模式匹配。首先我们引入目标串,模式串的概念,而字符串模式匹配就是查找模式串在目标串中的位置。2.brute-Force算法 brute-Force算法,我的理解是这样的。首先设目标串target="t0t1t2t3t4"...

    程序源代码:点击打开链接

    1.引入

        字符串模式匹配。首先我们引入目标串,模式串的概念,而字符串模式匹配就是查找模式串在目标串中的位置。

    2.brute-Force算法

        brute-Force算法,我的理解是这样的。首先设目标串target="t0t1t2t3t4",pattern="p0p1p2"。将p0与t0比较,若相同,则继续比较p1与t1。若不同,则从t1与p0开始比较。下面我们举个例子:

        target="aababcd",pattern="abcd";用target[i],pattern[j]分别表示target与pattern对应位置的字符(i,j初始为0)。

        首先target[i]的a与pattern[j]的a相同,于是i++,j++。此时target[i]的a与pattern[j]的b不同,于是i=i-j+1,j=0。比较target[i]的a与pattern[j]的a相同,于是i++,j++。此时target[i]的b与pattern[j]的b相同,于是i++,j++。此时target[i]的a与pattern[j]的c不相同,于是i=i-j+1,j=0。此时target[i]的b与pattern[j]的a不相同,于是i++,j=0。此时target[i]的a与pattern[j]的a相同,于是i++,j++。此时,target[i]的b与pattern[j]的b相同,于是i++,j++。此时target[i]的c与pattern[j]的c相同,于是i++,j++。此时target[i]的d与pattern的d相同,于是i++,j++。测试j=pattern.length=4,表示在目标串target中找到了模式串pattern,于是返回模式串在目标串中的位置3。

        下面是Brute-Force算法描述:

        设目标串中的字符为ti(0<=i<n),模式串中的字符为pj(0<=0<m,m<=n),将他们比较:

    (1)若ti=pj,继续比较ti+1与pj+1,直到j=m,则“ti-m+1……ti”与“p0……pm-1”匹配成功,返回模式串在目标串中匹配子串序号i-m+1。

    (2)若ti!=pj,表示ti-jtiti-j+m-1”与“p0…pjpm-1”匹配失败;目标串下一个匹配子串是“ti-j+1…ti-j+m”,继续比较ti-j+1与p0。此时,目标串回溯,从ti退回ti-j+1。

       程序流程图如下:


        代码如下:

    /**
     * 
     * @author 冯利
     * @version 创建时间:2018年5月18日 上午9:51:20
     */
    public class MyStringMatch {
    
    	/**
    	 * 从目标串的begin开始,查找模式串pattern在目标串中的位置
    	 * 
    	 * @auther 冯利
    	 * @version 创建时间:2018年5月18日 上午9:51:08
    	 * @param pattern
    	 * @param begin
    	 * @return
    	 */
    	public static int indexOf(String target, String pattern, int begin) {
    		// i为目标串target的索引
    		int i = begin;
    		// j为模式串pattern的索引
    		int j = 0;
    		// 输入要求
    		if (target == null || target.equals("") || pattern == null || pattern.equals("") || begin > target.length()) {
    			return -1;
    		}
    		// 循环,直到target或pattern被遍历完
    		do {
    			if (target.charAt(i) == pattern.charAt(j)) {
    				i++;
    				j++;
    			} else {
    				i = i - j + 1;
    				j = 0;
    			}
    		} while (i < target.length() && j < pattern.length());
    
    		// 模式串是否存在于目标串
    		if (j == pattern.length()) {
    			return i - pattern.length() ;
    		}
    		return -1;
    	}
    }   

        测试代码如下:

    public static void main(String[] args)
    	{
    		System.out.println(MyStringMatch.indexOf("aababcd", "cd", 0));
    	}

    运行结果如下:





    3.KMP算法

        由于暴力匹配算法目标串存在回溯,有缺陷,因此引入了Kmp这种不存在回溯的算法。而这个算法的核心是找出模式串中相同的最长前缀子串和后缀子串的长度k。Kmp算法如下:


        KMP算法与brute-Force算法的区别,在于当ti!=pj时,brute-Force算法要回溯,也就是i=i-j+1,j=0;而KMP算法将从ti与pk进行比较。所以求k是关键,接下来我们介绍求k的算法。

        首先,我们需要一个数组next来存模式串中每个字符(假设匹配时在这里出错)的k。举例:模式串“abcabc”的next数组


        KMP算法充分利用前一次的比较结果,由next[j]逐个递推计算得到next[j+1]。下面是一些说明:

    (1)约定next[0]=-1,-1表示下次匹配从tj+1与p0开始比较;约定next[1]=0,表示下次匹配从tj与p0开始比较。

    (2)对模式串当前字符序号j(0<=j<m),设next[j]=k,表示在“p0……pj-1”串中存在长度为k的相同的前缀子串和后缀子串,即“p0……pk-1”="pj-k……pj-1",0<=k<j且k取最大值。

    (3)对next[j+1]而言,求“p0……pj-1pj”中相同前后子串的长度k,需要比较前缀子串“p0……pk-1”与后缀子串“pj-k+1……pj”是否匹配。

        说明说完了,计算next数组的真正方法:假设target与pattern在ti于pj+1处匹配失败(即ti!=pj+1),并且已知“p0……pk-1”=“pj-k……pj-1”(也就是next[j]=k),此时只需要比较pk与pj是否相同。

        1.如果pk=pj,或k=-1时则next[j+1]=k+1=next[j]+1.

        2.如果pk!=pj,则在“p0……pj”串中寻找较短的相同前后缀子串(即令k=next[k],再比较pj与pk)。

        下面举个例子,求模式串“abcabdabcabcaa”的next数组

        当在j=12时匹配失败,则比较p11与p5(k=next[11]=5)。此时p11!=p5,于是k=next[5]=2。此时比较p11与p2,相等,于是next[j+1]=2+1=3。

        求next的流程图如下:


        至此,kmp的求next算法已经有了。这儿有一个改进了的求next数组的方法。下面介绍。

        当ti!=pj时,next[j]=k,若pk=pj,可知ti!=pk,则下次模式匹配串从pnext[k]开始比较。显然next[k]<next[j]越小,next[j]越小,模式串右移的距离越远,比较的次数也越少。下面举两个例子。

        模式串“abcabc”的next数组


        模式串“abcabdabcabcaa”的next数组


        改进了的求next流程图如下:



    kmp代码如下:

    /**
    	 * kmp模式匹配算法
    	 * 
    	 * @auther 冯利
    	 * @version 创建时间:2018年5月18日 下午9:38:43
    	 * @param target
    	 *            目标串
    	 * @param pattern
    	 *            模式串
    	 * @param begin
    	 *            从目标串中起始匹配位置
    	 * @return -1:表示匹配失败;其他表示pattern在target中的位置
    	 */
    	public static int indexOf_KMP(String target, String pattern, int begin) {
    		//未改进的next求法
    		//int next[] = getNextW(pattern);
    		//改进了的next求法
    		int next[]=getNext(pattern);
    		// i为目标串target的索引
    		int i = begin;
    		// j为模式串pattern的索引
    		int j = 0;
    		// 输入要求
    		if (target == null || target.equals("") || pattern == null || pattern.equals("") || begin > target.length()) {
    			return -1;
    		}
    		// 循环,直到target或pattern被遍历完
    		do {
    			if (target.charAt(i) == pattern.charAt(j)) {
    				i++;
    				j++;
    			} else {
    				j = next[j];
    				if (j == -1) {
    					i++;
    					j++;
    				}
    			}
    		} while (i < target.length() && j < pattern.length());
    
    		// 模式串是否存在于目标串
    		if (j == pattern.length()) {
    			return i - pattern.length();
    		}
    		return -1;
    	}
    
    	/**
    	 * 未改进的求next方法
    	 * @auther 冯利
    	 * @version 创建时间:2018年5月18日 下午9:45:59
    	 * @param pattern
    	 *            模式串
    	 * @return
    	 */
    	private static int[] getNextW(String pattern) {
    		int next[] = new int[pattern.length()];
    		next[0] = -1;
    		int j = 1;
    		while (j < pattern.length()) {
    			int k = next[j - 1];
    			while (true) {
    				if (k == -1 || pattern.charAt(j-1) == pattern.charAt(k)) {
    					next[j] = k + 1;
    					break;
    				} else {
    					k = next[k];
    				}
    			}
    			j++;
    		}
    		return next;
    	}
    	
    	/**
    	 * 改进了的求next方法
    	 * @auther 冯利
    	 * @version 创建时间:2018年5月18日 下午9:45:59
    	 * @param pattern
    	 *            模式串
    	 * @return
    	 */
    	private static int[] getNext(String pattern) {
    		int next[] = new int[pattern.length()];
    		next[0] = -1;
    		int j = 1;
    		while (j < pattern.length()) {
    			int k = next[j - 1];
    			while (true) {
    				if (k == -1 || pattern.charAt(j-1) == pattern.charAt(k)) {
    					next[j] = k + 1;
    					break;
    				} else {
    					k = next[k];
    				}
    			}
    			if(pattern.charAt(j)==pattern.charAt(next[j]))
    			{
    				next[j]=next[next[j]];
    			}
    			j++;
    		}
    		return next;
    	}

    测试代码:

    /**
     * 
     * @author 冯利
     * @version 创建时间:2018年5月18日 上午10:01:20
     */
    public class Main {
    	
    	public static void main(String[] args)
    	{
    		System.out.println(MyStringMatch.indexOf_Force("aababcd", "cd", 0));
    		System.out.println(MyStringMatch.indexOf_Force("abcdabcabbabcabc", "abcabc", 0));
    		System.out.println(MyStringMatch.indexOf_KMP("aababcd", "cd", 0));
    		System.out.println(MyStringMatch.indexOf_KMP("abcdabcabbabcabc", "abcabc", 0));
    	}
    }

    运行结果:


    程序源码:点击打开链接




        

            

     












        
    展开全文
  • 算法案例分析—字符串模式匹配算法

    千次阅读 多人点赞 2020-09-09 19:49:13
    今天来和大家分享一个关于字符串比较的模式匹配算法,在数据结构中对字符串的相关操作中,对子串的定位操作通常称为串的模式匹配,同样他也是各种串处理中最重要的操作之一,同时子串也称为模式串,关于主串和模式串...

    目录

    一、朴素的模式匹配算法

    二、KMP算法(改进的模式匹配算法)


    hello!大家好哇,我是灰小猿,一个超会写bug的沙雕程序猿!

    今天来和大家分享一个关于字符串比较的模式匹配算法,在数据结构中对字符串的相关操作中,对子串的定位操作通常称为串的模式匹配,同样他也是各种串处理中最重要的操作之一,同时子串也称为模式串,关于主串和模式串的匹配算法常用的主要有两种:朴素的模式匹配算法和KMP算法(改进的模式匹配算法),接下来将分别对这两种算法进行分析。

    一、朴素的模式匹配算法

    朴素的模式匹配算法也被称为布鲁特—福斯算法,其基本思想是:从主串的第一个字符起与模式串的第一个字符相比较,若相等,则逐一对之后的字符进行比较,否则从主串的第二个字符与模式串的第一个字符重新比较,直到模式串中的每一个字符依次与主串中连续的字符序列相匹配为止,这时就称为匹配成功,如果不能在主串中找到与模式串相匹配的内容,则称为匹配失败。

    接下来举一个例子,以字符数组存储字符串,实现朴素的模式匹配算法。

    //传入主串s和模式串t,同时设定从主串中开始匹配的位置pos
    int index(char s[],char t[],int pos) {
    	int i,j,slen,tlen;
    	i = pos;
    	j = 0;
    	slen = s.length;	//获取到主串的长度
    	tlen = t.length;	//获取到模式串的长度
    	while (i<slen && j<tlen) {
    		if (s[i] == t[j]) {
    			i++;
    			j++;
    		}
    		else {
    			i = i-j+1;
    			j=0;
    		}		
    	}
    	if (j>=tlen) {
    		return i-tlen;
    	}
    	return 1;
    }

     

    二、KMP算法(改进的模式匹配算法)

    KMP算法是上一个算法的改进,相比于朴素的模式匹配算法,KMP算法在进行主串和模式串的匹配过程中,每当匹配过程中出现相比较的字符不相等时,不需要回退主串的字符位置指针,而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离,再继续进行比较。

    设模式串为“P0...P(m-1)”,KMP匹配算法的思想是:当模式串中的字符Pj与主串中相应的字符Si不相等时,因其前j个字符(“P0...P(j-1)”)已经获得了成功的匹配,所以若模式串中的“P0...P(k-1)”与“P(j-k)...P(j-1)”相同,这时可令P0与Si相比较,从而使i无需回退。

    在KMP算法中,依据模式串的next函数值可以实现子串的滑动,若令next[j]=k,则next[j]表示当模式串中的Pj与主串中相应的字符不相等时,令模式串的Pnext[j]与主串的相应字符进行比较,

    关于next函数有如下的定义:

    以下是求模式串的next函数的程序:

    //求模式串p的next函数值,并存入数组next中
    void Get_next(char *p,int next[])
    {
    	int i,j,slen;
    	slen = strlen(p);	//获取到模式串的长度
    	i=0;
    	while (i<slen) {
    		if (j==-1||p[i]==p[j]) {
    			++i;
    			++j;
    			next[i] = j;
    		} else {
    			j = next[j];
    		}
    	}
    }

    在获取到的next函数后,

    在KMP模式匹配算法中,设模式串的第一个字符下标为0,则KMP算法如下:

    /*利用模式串p的next函数,求p在主串s中从第pos个字符开始的位置*/
    /*若匹配成功,返回模式串在主串的位置下标,否则返回-1 */
    int Index_KMP(char *s,char *p,int pos,int next[])
    {
    	int i,j,slen,plen;
    	i=pos-1;
    	j=-1;
    	slen = strlen(s);	//求主串的长度
    	plen = strlen(p);	//求模式串的长度
    	while (i<slen && j<plen) {
    		if (j==-1||s[i]==p[j]) {
    			++i;
    			++j;
    		} else {
    			j=next[j];
    		}
    	}
    	if (j>=plen) {
    		return i-plen;
    	}
    	else {
    		return -1
    	}
    		
    }

    关于字符串模式匹配算法就分享到这里,有不足的地方还希望各位大佬一起指正,

    觉得不错记得点赞关注哟!

    大灰狼陪你一起进步!

    展开全文
  • 一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下 主串s=ababcabcacbab 从串t=abcac 一般匹配方法如下图所示 代码如下 int index(string s,string t) {  int i=0,j=0;  int l1=s.length();  ...

    一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下

    主串s=ababcabcacbab

    从串t=abcac

    一般匹配方法如下图所示

    图片

    代码如下

    int index(string s,string t)
    {
        int i=0,j=0;
        int l1=s.length();
        int l2=t.length();
        while(i<=l1-1&&j<=l2-1)
        {
            if(s[i]==t[j])
            {
                ++i;
                ++j;
            }
            else
            {
                if(j==0)
                {
                    ++i;
                }
                else
                {
                    i=i-j+2;
                    j=0;
                }

            }
            //cout<<"i="<<i<<"j="<<j<<endl;
        }
        if(j>l2-1) return i-l2;
        else return 0;
    }

    这样算下来的时间复杂度是O(l1*l2),因为每次只要中间发生字符串s[i]和t[j]不相等,这种算法会把字符串t的索引置为0,而主串s也是从之前开始匹配的i加一个1,其实我们可以发现,中间有些比较是不必要的,比如从第三趟比较就可以看出主串中第4,5,8个字符串是‘b’,'c','a',(对应模式串中的第2,3,4个字符)。而模式串t中第一个字符是a,所以其实不需要和这几个字符相比较了,只需要将模式向右滑动3个字符即可。这样的匹配过程中,实际上主串i没有回溯,只是模式串的j在变化,就降低了时间复杂度为O(l1+l2),这也就是kmp算法。

    kmp算法每趟比较过程让模式串向后滑动一个合适的位置,这个合适的位置我们可以算出来,一般称这个位置叫next表。

    先写出next表的定义,接下来再解释为什么这样定义

     

    结合这个图来解释

    先说一下,上面两个图中的S0和T0分别代表的是两个穿的长度,真正的字符串都从下标1开始。

    1)当j=1时,也就是说模式串的第一个字符就与当前位置s对应的字符不同,此时主串的下标应该+1,再和模式串第一个字符进行比较;

    2)当两个串匹配到此处时,前j-1个字符都是匹配的,到了第j个字符就不同了,此时需要把字符串t向右移动max{k}个位置。

    这个k应该满足1<k<j并且p1...pk-1=pj-k+1...pj-1.k的值可能有多个,为了不使向右移动丢失可能的匹配,选择最大的一个k,也就是max{k},其最大值为j-1;

    3)除了上面两种情况,发生匹配时,主串指针i不回溯,在最坏情况下,模式串从第1个字符开始与主串第i个字符比较,以便不丢失可能的匹配。

    上面讲解的next函数表的定义,然后下面是求next函数表的代码以及实现kmp算法。篇幅有点长,转到下一篇讲。

     

    展开全文
  • 字符串模式匹配KMP算法详解(Python语言)

    万次阅读 多人点赞 2018-08-17 10:59:03
    问题描述  主为′ababcabcacbab′′ababcabcacbab′'ababcabcacbab',模式串为′abcac′′abcac′'abcac',现在要求模式串在主中出现的...如果不相等,则从主的第二个位置重新和模式串字符匹配。完整匹配...
  • KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法,同时前面的例子中也描述了子串移动位置的...
  • 数据结构 基于字符串模式匹配算法的病毒感染检测问题实验目的实验内容实验提示 实验目的 1.掌握字符串的顺序存储表示方法。 2.掌握字符串模式匹配算法BF算法或KMP算法的实现。 实验内容 问题描述 医学研究者最近发现...
  • HDUOJ 1634 算法4-6:KMP字符串模式匹配算法实现 题目链接 题目描述 KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏...
  • lua之字符串模式匹配

    万次阅读 2017-09-27 17:48:15
    在string库中功能最强大的函数是: 复制代码代码如下: string.find(字符串查找) ...这些函数都是基于模式匹配的。与其他脚本语言不同的是,Lua并不使用POSIX规范的正则表达式[4](也写作regexp)来进
  • 模式匹配算法 求子位置的定位函数 Index(S, P, pos) 求子的定位操作通常称作模式匹配(其中子串P称为模式)。 算法1:朴素模式匹配算法/简单匹配算法(Brute-Force算法,简称BF算法) 从目标主s=...
  • 介绍 MySQL 中实现字符串模糊查找的两种方法:LIKE 运算符以及正则表达式函数 REGEXP_LIKE 和 REGEXP 、RLIKE 运算符。
  • 字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为 O(m*n);KMP 匹配算法。可以证明它的时间复杂度为 O(m+n). 。 一.  简单匹配算法 先来看一个...
  • Shell:字符串模式匹配# %

    千次阅读 2013-12-05 21:33:31
    bash提供了可操作路径名称字符串和其它字符串的字符串模式匹配运算符。 注意区分和通配符的区别:http://blog.sina.com.cn/s/blog_ac9fdc0b0101ls9h.html 还有正则表达式的区别:...
  • KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n),KMP匹配算法,可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的...
  • LeetCode刷题笔记 字符串 字符串匹配

    千次阅读 2021-11-01 13:18:44
    输入一个母字符串和一个子字符串,输出一个整数,表示子字符串在母字符串的位置,若不存在则返回-1。 输入:haystack = “hello”, needle = “ll” 输出:2 解析: ​ 解决本题一种简单的思路是暴力匹配:首先将...
  • Linux shell 字符串模式匹配运算符

    千次阅读 2014-10-31 12:31:05
    Linux 的字符串截取很有用。有八种方法。
  • 字符串模式匹配算法--详解KMP算法

    千次阅读 热门讨论 2014-10-26 10:14:54
    在软考的复习中,看到过几次 字符串模式匹配算法。看起来挺难的。所以花了点时间查了查关于字符串匹配的算法。下面详细介绍一下KMP模式匹配算法 以及next[j]函数如何计算。
  • *串的模式匹配-BF算法 *找到相同的字符串输出在原字符串中的位置 代表匹配字符串在原字符串中的位置 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define STRSIZE 255//字符串的...
  • 字符串模式匹配——KMP

    千次阅读 2016-12-29 12:37:51
    本文从常见的字符串模式匹配开始,以通俗易懂的语言阐述了KMP算法原理和适用的场景,编写尽量避免使用晦涩的语言及复杂的数学公式,只为作为学习笔记记录个人的理解过程,追求理论的同学请绕行到《算法导论》。
  • kmp字符串模式匹配中next函数值的算法

    万次阅读 多人点赞 2017-04-10 16:41:18
    模式串 a b a a b c a c next[j] 0 1 1 2 2 3 1 2各个位的解释 1.前两位必定为0和1。 2.计算第三位的时候,看第二位b的next值,为1,则把b和1对应的a进行比较,不同,则第三位a的next的值为1,因为一直比到最前一...
  • 模式匹配是数据结构中字符串的一种基本操作,它用于在一条字符串中寻找与另一条子串相同的所有子串。 例如 在"hjh123abc"中寻找"hjh" 二、简单模式匹配 暴力匹配 int Index(String S,String T){ int i=1,j=1; ...
  • KMP字符串模式匹配详解

    万次阅读 2013-02-12 19:26:06
    个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了,确实说得很“详细”,耐心地把它看完肯定会有所收获的~~,另外有关模式函数值next[i]确实有很多版本啊,在另外一些面向对象的算法描述书中也有...
  • 字符串匹配算法(单模式串)

    千次阅读 2019-02-17 22:37:22
    本文是数据结构与算法之美的学习笔记 ...字符串匹配算法有:单模式匹配算法(BF算法,RK算法,BM算法,KMP算法), 多模式匹配算法(Trie树,AC自动机) BF(Brute Force)算法 基础概念:如果我...
  • 《C语言》字符串匹配(BF算法+KMP算法)

    千次阅读 多人点赞 2020-05-02 16:07:17
    字符串匹配 【问题描述】 对于字符串S和T,若T是S子串,返回T在S中的位置(T的首字符在S中对应的下标),否则返回-1. 【问题求解】 采用直接穷举法求解,称为BF算法。该算法从S的每一个字符开始查找,看T是否会出现...
  • 经典算法题09-字符串模式匹配KMP

    千次阅读 2016-06-29 12:38:46
    提问字符串模式匹配指的是,找出特定的字符串在一个较长的字符串中出现的位置。 有一个长字符串”ababcabababdc”,请问子串”babdc”出现的位置是哪里? 二. 思路在字符串模式匹配的学习中,可能首先就会想起将...
  • python 中如何匹配字符串

    千次阅读 2021-02-03 02:50:57
    1. re.match 尝试从字符串的起始位置匹配一个模式,如果不是起始位置匹配成功的话,match()就返回none。importreline="thishdr-biz123modelserver456"pattern=r"123"matchObj=re.match(pattern,line)2. re.search ...
  • python正则表达式如何匹配字符串

    千次阅读 2021-02-10 12:10:57
    python正则表达式匹配字符串的方法:1、使用【(.+?)】这个正则表达式来提取单个位置的字符串;2、使用【(?P…)】这个正则表达式【匹配连续多个位置的字符串。python正则表达式匹配字符串的方法:一、单个位置的字符...
  • 字符串模式匹配(KMP)算法

    千次阅读 2018-09-10 09:40:51
    给定一个主(以 S 代替)和模式(以 P 代替),要求找出 P 在 S 中出现的位置,此即模式匹配问题。 Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 443,729
精华内容 177,491
关键字:

字符串模式匹配