精华内容
下载资源
问答
  • 字符串模式匹配

    2018-06-08 01:12:35
    字符串模式匹配问题:在目标串TTT中查找是否有与模式串PPP匹配的子串。已经有很多算法用来解决这个问题(参考string matching algorithms),这里主要介绍朴素的模式匹配算法和KMP算法。...

    字符串模式匹配问题:在目标串T中查找是否有与模式串P匹配的子串。已经有很多算法用来解决这个问题(参考string matching algorithms),下面主要介绍朴素的模式匹配算法和KMP算法

    朴素的模式匹配

    这个模式匹配方法又被称为Brute-Force算法。

    该算法首先将目标串T的第一个字符和模式串P的第一个字符比较,若相等,继续逐个比较后续字符;若不等,从目标串T的下一字符开始,重新与模式串P的第一个字符进行比较。直到目标串T的一个连续字符序列(子串)与模式串P相等 ,则匹配成功,返回模式串P在目标串T中的匹配位置;否则,匹配失败,返回值 1

    Brute-Force算法每次遇到匹配不成功的情况时,目标串的扫描指针都要移到本次匹配开始位置的下一个字符继续与模式串进行匹配(回溯)。Brute-Force算法在最坏情况下总的比较次数为(lengthTlengthP+1)lengthP

    C码实现如下:

    /*Brute-Force算法*/
    int brute_force_string_matching(char *target, char *pattern)
    {
        int indexT, indexP;
        int lenT = strlen(target);
        int lenP = strlen(pattern);
    
        for (indexT = 0; indexT < lenT - lenP + 1; indexT++)
        {
            for (indexP = 0; indexP < lenP; indexP++)
            {
                if (target[indexT + indexP] != pattern[indexP])
                {
                    break;
                }
            }
    
            if (indexP == lenP)
            {
                return indexT;
            }
        } 
    
        return -1;
    }

    KMP算法

    展开全文
  • KMP字符串模式匹配

    2015-02-26 17:51:34
  • KMP字符串模式匹配算法 当我们使用简单字符串模式匹配算法时,时间复杂度为O(n*m),这里n为目标串的长度,m为模式串的长度。在循环的过程中,有很多次匹配其实存在回溯,浪费了很多时间。可以根据模式串本身的性质...

    KMP字符串模式匹配算法

    当我们使用简单字符串模式匹配算法时,时间复杂度为O(n*m),这里n为目标串的长度,m为模式串的长度。在循环的过程中,有很多次匹配其实存在回溯,浪费了很多时间。可以根据模式串本身的性质来设计一个新的高效算法,即跳过肯定不匹配的循环,而直接从左边子串已经相同的位置开始比较,时间复杂度大大降低,该算法就是KMP字符串模式匹配算法。

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int KMPIndexHelp(const string &T,const string &P,int pos,int next[]){
        int i=pos,j=0;
        while(i<T.length() && j<P.length())
        {
            if(j==-1)
            {
            i++; j=0;
            }
            else if(T[i]==P[j]){
                i++; j++;
            }
            else
            {
                j=next[j];
            }
        }
    
        if(j<P.length()) return false;
        else return i-j;
    }
    
    void GetNext(const string &P,int next[])
    {
        next[0]=-1;
        int j=0,k=-1;
        while(j<P.length()-1)
        {
            if(k==-1)
            {
                next[j+1]=0;
                j++;k=0;
            }
            else if(P[k]==P[j])
            {
                next[j+1]=k+1;
                j++;k++;
            }
            else
            {
                k=next[k];
            }
        }
    }
    
    int KMPIndex(const string &T,const string &P,int pos=0){
       int *next=new int[P.length()];
       GetNext(P,next);
       int result=KMPIndexHelp(T,P,pos,next);
       delete []next;
       return result;
    }
    int main()
    {
        int r=0;
        string T="acabaabaabcacx";
        string P="abaabcac";
        cout << KMPIndex(T,P,r) <<endl;
        return 0;
    }
    
    
    展开全文
  • 字符串模式匹配(KMP) 给定一个字符串 text 和一个模式串 pattern,求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。 输入格式: 输入...

    字符串模式匹配(KMP)

    给定一个字符串 text 和一个模式串 pattern,求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。

    输入格式:

    输入共两行,分别是字符串text 和模式串pattern。

    输出格式:

    输出一个整数,表示 pattern 在 text 中的出现次数。

    输入样例1:

    zyzyzyz
    zyz

    输出样例1:

    3

    输入样例2:

    AABAACAADAABAABA
    AABA

    输出样例2:

    3

    数据范围与提示:

    1≤text, pattern 的长度 ≤10
    ​6
    ​​ , text、pattern 仅包含大小写字母。
    本题关于KMP算法这一点,我能力有限,无法做出更加详细的解释,可以参考july的关于kmp的博客
    点击前往july博客
    这道题就是在kmp的基础上,如果找到一个子串后,不要return,先让计数器++,再让i–,即返回到上一个字符,让j=next[j-1],即假设第j个字符失配,然后继续执行相关操作即可.还有一点就是,作者能力有限,不知道为什么一改成优化后的next数组就不对,不优化就对了,如果有谁知道的话,欢迎下方评论指教.

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    char s[1000005],p[1000005];
    int Next[1000005];
    void GetNext(int pLen){
    	int k=-1;
    	Next[0]=-1;
    	int j=0;
    	while(j<pLen){
    		if(k==-1||p[j]==p[k]){
    			j++;
    			k++;
    			Next[j]=k;
    		}else {
    			k=Next[k];
    		}
    	}
    }
    int KMP(int sLen,int pLen){
    	int i=0;
    	int j=0;
    	int cnt=0;
    	while(i<sLen&&j<pLen){
    		if(j==-1||s[i]==p[j]){
    			i++;
    			j++;
    		}else{
    			j=Next[j];
    		}
    		if(j==pLen)cnt++,j=Next[j-1],i--;
    	}
    	return cnt; 
    }
    int main(){
    	int sLen,pLen;
    	for(sLen=0;(s[sLen]=getchar())!='\n';sLen++);
    	for(pLen=0;(p[pLen]=getchar())!='\n';pLen++);
    	GetNext(pLen);
    	cout<<KMP(sLen,pLen);
    }
    
    展开全文
  • 字符串模式匹配KMP算法 字符串模式匹配指的是,找出特定的模式串在一个较长的字符串中出现的位置。 朴素的模式匹配算法 很直观的可以写出下面的代码,来找出模式串在一个长字符串中出现的位置。 ...
  • 数据结构之字符串模式匹配

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

    2017-04-05 15:19:03
    字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽     本文内容框架: §1 Boyer-Moore算法 §2 Horspool算法 §3 Sunday算法 §4 KMP算算法 §5 KR算法 §6 AC...
  • 利用KMP算法进行字符串模式匹配
  • KMP字符串模式匹配算法

    千次阅读 2016-09-23 11:39:07
    KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数: ...
  • 算法案例分析—字符串模式匹配算法

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

    千次阅读 2016-12-29 12:37:51
    本文从常见的字符串模式匹配开始,以通俗易懂的语言阐述了KMP算法原理和适用的场景,编写尽量避免使用晦涩的语言及复杂的数学公式,只为作为学习笔记记录个人的理解过程,追求理论的同学请绕行到《算法导论》。
  • KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先...
  • KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法,同时前面的例子中也描述了子串移动位置的...
  • 一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下 主串s=ababcabcacbab 从串t=abcac 一般匹配方法如下图所示 代码如下 int index(string s,string t) {  int i=0,j=0;  int l1=s.length();  ...
  • 之前对于字符串模式匹配的了解仅限于那几个API函数和暴力求解方法,没有真正地探讨过关于字符串匹配的问题,今天因为一些原因看到了这个问题引发了我的兴致,故研究了一下sunday算法。1.sunday思路sunday算法是从...
  • 字符串模式匹配问题在很多方面我们都会见到,简单的说就是在父串中,找到与子串相等的字符串,一般我们会返回匹配成功后的位置起点。BF算法BF算法我们一般称为“朴素”算法,或者男朋友算法,他的实现很简单,就是...
  • HDUOJ 1634 算法4-6:KMP字符串模式匹配算法实现 题目链接 题目描述 KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏...
  • 经典算法题09-字符串模式匹配KMP

    千次阅读 2016-06-29 12:38:46
    提问字符串模式匹配指的是,找出特定的字符串在一个较长的字符串中出现的位置。 有一个长字符串”ababcabababdc”,请问子串”babdc”出现的位置是哪里? 二. 思路在字符串模式匹配的学习中,可能首先就会想起将...
  • 如果使用者不在乎字符串模式匹配的时效性,或者pattern只使用一次,选re.match。因为re.match使用方法比较容易理解和掌握,也比较清晰明了 如果使用者非常在乎时效性,同时同一个pattern需要使用多次,那就强烈建议...
  • 回溯的字符串模式匹配

    千次阅读 2013-10-28 11:22:30
    //回溯的字符串模式匹配 int strfind(char* str,char* mode) { int i=0; int j=0; while(i { //如果两个字符相同,则继续下一个匹配 if(str[i]==mode[j]) { //如果发现已经匹配到最后一个字符,则返回成

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,669
精华内容 11,067
关键字:

字符串模式匹配