1 // 根据算法引论一书中的说明写的程序 2 #include <stdio.h> 3 #include <string> 4 #define MAX_N 1000 5 using std::string; 6 7 int next[MAX_N]; 8 9 void generate_next(const string& pattern) {10 next[0] = -1;11 for(int i = 1; i < pattern.length(); ++i) {12 int j = next[i-1];13 while (j >= 0 && pattern[j] != pattern[i-1])14 j = next[j];15 16 // either patt...
kmp的代码很短,但是不太容易理解,还是先说明一下这个算法过程吧。朴素的字符串匹配大家都懂,但是效率不高,原因在哪里?匹配过程没有充分利用已经匹配好的模版的信息,比如说,i是文本串当前字符的下标,j是要匹配的模版串当前正在匹配的字符的下标。(下标都从零开始)当匹配到i = 4, j = 4的时候失配了,朴素的匹配做法是往右边移一位然后从j开始扫,这样做效率很低。不难发现前面已经匹配好的串ab是相同的最大前缀后缀。把串...
输入第一行一个整数N,表示测试数据组数。接下来的N*2行,每两行表示一个测试数据。在每一个测试数据中,第一行为模式串,由不超过10^4个大写字母组成,第二行为原串,由不超过10^6个大写字母组成。其中N<=20输出对于每一个测试数据,按照它们在输入中出现的顺序输出一行Ans,表示模式串在原串中出现的次数。样例输入5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD样例输出3
1
3
1
0 1 #includ...
今天又看了一遍KMP,感觉真的懂了...就来这儿发一下心得吧.KMP算法其实就是暴力的改进版.让我们看看暴力的匹配.Original string: ababababcbbababababc
Pattern string: abababc步骤:ababababcbbababababc
abababc....中间一些步骤ababababcbbababababcabababc这里a和c匹配不了了,传统的作法会从第二个字符`b‘开始匹配.明显不行又跳出.即:ababababcbbababababca...再从第三个字符`a‘开始:ababababc...abababc现在匹配了.继续重复...
题目链接:https://cn.vjudge.net/problem/HDU-3613 After an uphill battle, General Li won a great victory. Now the head of state decide to reward him with honor and treasures for his great exploit. One of these treasures is a necklace made up of 26 different kinds
of gemstones, and the length of the necklace is n. (That is to say: n
gemstones are stringed together to constitute this necklace, and ...
引言一个算是冷门的算法(在竞赛上),不过其算法思想值得深究。前置知识kmp的算法思想,具体可以参考 → Click heretrie树(字典树)。正文问题定义:给定两个字符串 S 和 T(长度分别为 n 和 m),下标从 0 开始,定义 extend[i] 等于 S[i]...S[n-1] 与 T 的最长相同前缀的长度,求出所有的 extend[i]。举个例子,看下表:i01234567SaaaaabbbTaaaaacextend[i]54321000为什么说这是 KMP 算法的扩展呢?显然,如果在 S 的若干个位置...
作者:July。
出处:http://blog.csdn.net/v_JULY_v/。引记 此前一天,一位MS的朋友邀我一起去与他讨论高速排序,红黑树,字典树,B树、后缀树,包含KMP算法,只有在解说KMP算法的时候,言语磕磕碰碰,我想,原因有二:1、博客内的东西不常回想,忘了不少;2、便是我对KMP算法的理解还不够彻底,自不用说解说自如,运用自如了。所以,特再写本篇文章。因为此前,个人已经写过关于KMP算法的两篇文章,所以,本文名为:KMP算法之总...
1/* 核心代码 */ 2 3 4 5 #include<iostream>6 #include<string>7 8usingnamespace std;9constint N=100005;
1011void getNext(string p,int *next)
12{
13int j,k;
14 next[0]=-1;
15 j=0;
16 k=-1;
17while(j<p.length()-1)
18 {
19if(k==-1||p[j]==p[k]) //匹配的情况下,p[j]==p[k]20 {
21 j++;
22 k++;
23 next[j]=k;
24 }
25else/...
关于KMP算法,看了很多博客,自己也做了一些字符串匹配之后,总算弄懂一些了,但是可能还要进一步深入研究,先写一部分吧,这部分足够应对笔试的nextval和next问题了。关于如何求next:先给出一个字符串“ababaabab” j 1 2 3 4 5 6 7 8 9 i a b a b a a b a b next 0 1 1 2 3 4 2 3 4nextval 0 1 0 1 1 4 1 0 1next怎么求呢:首先,要了解两个概念:"前缀"和"后缀"...
看了一晚上才算看明白,明天继续看从头到尾彻底理解KMPpublic class KmpSearch {public static int indexOf(String s, String p) {if (p.length() == 0) return 0;int[] next = new int[p.length()];getNext(p, next);int i = 0;int j = 0;int sLen = s.length();int pLen = p.length();while (i < sLen && j < pLen) {if (j == -1 || s.charAt(i) == p.charAt(j)) {i++;j++;} else {j = next[j];}}if (j == pLen) {return i - j;} ...
首先从直观上看KMP存在的价值:一般在遇到字符串匹配的问题的时候,一种朴素的比较方式就是int BFMatch(char *s,char *p)
{int i,j;i=0;while(i<strlen(s)){j=0;while(s[i]==p[j]&&j<strlen(p)){i++;j++;}if(j==strlen(p))return i-strlen(p);i=i-j+1; //指针i回溯}return -1;
}S: ababcababa
P: ababa BF算法匹配的步骤如下 i=0 i=1 ...
KMP算法 从零开始大部分来自他人博客,蒟蒻只是总结学习引言
字符串匹配。给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置.char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";暴力解法如果当前字符匹配成功(即S[i] == P[j]),则i++,j++,继续匹配下一个字符;
如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被...
KMP算法主要用于解决包含问题,即存在两个字符串str1和str2,判断str1字符串中是否包含字符串str2,包含则返回str2对应在str1中的字符串的首字符的位置,否则返回-1;例如:str1="abc123def" str2="123d" ,str1的长度为N, str2的长度为M,则返回3; 那么如何解决这类问题呢?正常的解法所用时间复杂度为O(N*M),即一个一个字符进行匹配,匹配不成功,则str1索引向后移动一位,str2重新从首字符进行匹配。 使用KMP算法...
KMP算法1. 算法介绍KMP是一个解决模式串在文本串是否出现过,若出现过,最早出现的位置的算法Knuth-Morris-Pratt 字符串查找算法,简称“KMP算法”,此算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977年联合发表,故使用三人姓氏命名KMP方法利用之前判断过的信息,new 一个数组,保存模式串前后最长公共子序列的长度,每次回溯时,通过next数组找到,前面匹配过的位置,省去了大量的实践2. 应用场景-字符串匹配s...
字符串匹配(string match)是在实际工程中经常会碰到的问题,通常其输入是原字符串(String)和子串(又称模式,Pattern)组成,输出为子串在原字符串中的首次出现的位置。通常精确的字符串搜索算法包括朴素搜索算法,KMP, BM(Boyer Moore), sunday, robin-karp 以及 bitap。下面分析朴素搜索算法和KMP这两种方法并给出其实现。假设原字符T串长度N,子串P长度为M。
1.NAIVE—STRING—MATCHING.
朴素算法,该方法又称暴力搜索,也是最容...