kmp 订阅
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]  。 展开全文
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]  。
信息
时间复杂度
O(m+n) [1]
外文名
The Knuth-Morris-Pratt Algorithm [1]
发现者
D.E.Knuth等 [1]
中文名
KMP算法 [1]
算法基础
Brute-Force [2]
应    用
字符串匹配 [1]
kmp算法简介
KMP算法是三位学者在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退,从而可以大大提高效率 [2]  。
收起全文
精华内容
参与话题
问答
  • KMP算法

    千次阅读 多人点赞 2017-03-01 21:36:21
    KMP算法

    KMP算法
    1 理解KMP算法的几个要点
    (1) 首先我们需要知道为什么需要KMP算法?
    减少不必要的回溯
    (2) 怎样减少不必要的回溯?
    借助next数组(当模式匹配串T失配的时候,NEXT数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配)

    (3) 怎样产生next数组?

     

    (4) 什么是前缀和后缀 


     2核心在于next数组(next数组就相当于索引)
    void get_next( String T, int *next )
    {
    	j = 0;
    	i = 1;
    	next[1] = 0;
    	while( i < T[0] )
    	{
    		if( 0==j || T[i] == T[j] )
    		{
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else
    		{
    			j = next[j];
    /*这里的j又被重新打回去重新计数,j就是一个计数器,计数着不匹配的这个元素之前的前
    缀和后缀中有几个相同的元素。*/
    		}
    	}
    }
    


    展开全文
  • kmp算法白话解析

    千次阅读 多人点赞 2018-11-17 16:12:49
    kmp

    字符串匹配就是在一个主串中找到待匹配串的位置,一般是返回第一次出现的位置.一般思路是从待匹配串的第一个字符开始逐个与主串中的字符匹配,如果匹配成功,则主串和待匹配串都后移一位,匹配下一个字符,如果匹配不成功,待匹配串从头开始与主串的下一位匹配.这就是朴素匹配.下面是代码

    int Index (String S, String T) {
    	int i = 1, j = 1;
    	while (i <= S.length() && j <= T.length()) {
    		if (S[i] == T[j]) {
    			++i;
    			++j;
    		} else {
    			i = i - j + 2;
    			j = 1;
    		}
    	}
    	if (j > T.length())
    		return i - T.length();
    	else 
    		return 0;
    }
    //算法最坏时间复杂度为O(n*m),n,m分别为主串和待匹配串的长度
    

    这种简单匹配有一个简单的问题就是,出现大量没有必要的回退,如
    a b a b c a b c a c b a b
    ..a b c a c
    此时c与b不匹配,带匹配串要回到第一个字符a处,而主串要回到第二个b处,但是回退后主串和待匹配串此时要匹配的字符肯定不同,这是我们在上一次匹配是就得到的结论,所以这种回退是没必要的,但怎样才是回退最少呢?由于此时c与b不匹配,但是c之前的都已经匹配了,假如说主串不动,待匹配串向右滑动,那么只需要让待匹配串向右滑动一个距离,使c前面中的字符尽可能多的与主串中的匹配成功,这样就能使主串回退的少,待匹配串也回退的少.如果这句话没理解的话,换句话说就是在在主串和待匹配串已经匹配成功的这部分中,挑主串中后缀中与待匹配串前缀中相同的部分的最大长度.
    在这里插入图片描述
    如图,此时C与B不匹配,回退就是让蓝色部分尽可能的长,那么回退的就会少.也就是这部分再次比较了.好了,到这就应该明白我们要干什么了,但是怎么做呢?我们来想想,我们要找的就是不匹配字符串之前的那部分已经匹配的部分中,主串的后缀和待匹配串的前缀相同的最大部分,而我们要找的这部分所在的部分正好就是已经匹配了的部分,即待匹配串发生不匹配处之前的部分,那么其实就和主串没有关系了,只需要在待匹配串的发生不匹配处以前的子串中找到前后缀相同的最大部分就行了.
    那好,现在简单了,只需要分析待匹配串的前后缀就行了,但是是分析谁的前后缀呢,是整个待匹配串的前后缀还是待匹配串的子串的前后缀呢?答案肯定是后者,因为我们每次在发生不匹配时才决定要后退多少步(前后缀相同部分的长度),而不匹配可能在任意一个字符处发生,也就是说,每一个字符都应该对应一个后退值,以便于在发生不匹配是,确定后退多少步.而这个步长我们记录下来就叫做next值,顾名思义,就是发生不匹配,下一步得后退多少.
    那么next值的求法就是整个算法的关键,这个算法就是KMP算法.
    那么next怎么求呢?如果你之前看过其他文章,肯定会看到一个公式,
    next[j]={0j=1Max[k1<k<jP1...Pk1=Pjk+1...Pj1]1next[j] = \begin{cases} 0 ,当j=1时\\ Max [k|1 < k < j 且`P1...Pk-1 = 'Pj-k+1...Pj-1']\\ 1,其他情况\\ \end{cases}
    首先说明,这是一个很恶心的公式,我TM看不懂.来说说我们该怎么做吧.
    通过刚才的分析,大家应该也已经明白.就是找待匹配串的各个子串的最大公共前后缀长度

    求next方法一

    找待匹配串中每一个字符前的子串中前后缀最长公共部分

    next = 前后缀最长公共部分+1

    因为最长公共部分是已经匹配了的,所以要从公共部分的下一个开始比较,而next的值就是下一次比较时开始的位置.
    这里需要注意两点,
    一.待匹配串的第一个字符是不需要回退的,因为它就是回退的最后一个了.
    二.子串前后缀没有重合部分且子串不为空,即需要从子串头开始匹配,所以next=1
    串在数组中从下标1开始存储,所以j从1开始

    模式串 A B A B A B B
    j 1 2 3 4 5 6 7

    这里说一下什么是前后缀,前缀就是一个字符串从前往后,长度小于原串的子串,后缀同理,从后往前.如abcd,前缀有a,ab,abc,后缀有d,cd,bcd.

    1. 当j=1时发生不匹配,子串为空,next = 0
    2. 当j=2时发生不匹配,子串为 A,前后缀公共部分是空, next = 1
    3. 当j=3时发生不匹配,子串为 AB,前后缀公共部分为空, next = 1,
    4. 当j=4时发生不匹配,子串为 ABA,前后缀公共部分是A, next = 2
    5. 当j=5时发生不匹配,子串为 ABAB,前后缀公共部分是AB, next = 3
    6. 当j=6时发生不匹配,子串为 ABABA,前后缀公共部分是ABA, next = 4
    7. 当j=7时发生不匹配,子串为 ABABAB,前后缀公共部分是ABAB, next = 5
    模式串 A B A B A B B
    j 1 2 3 4 5 6 7
    next 0 1 1 2 3 4 5

    求next方法二

    1. next[1] = 0, next[2] = 1,
    2. k = next[j - 1],
    3. 若S[j-1] == S[k] ,则next[j] = k+1;
      若S[j-1] != S[k] , 则 k = next[k];若k != 0,则跳到3,若k 等于 0,next[j] = 1
    模式串 A B A B A B B
    j 1 2 3 4 5 6 7
    next 0 1
    1. j = 3, k = next[j-1] = next[2] = 1,
      (S[j-1] = S[2] = B) != (S[k] = S[1] = A),
      k = next[k] = next[1] = 0,
      next[j] = next[3] = 1;
    2. j = 4, k = next[j-1] = next[3] = 1,
      (S[j-1] = S[3] = A) == (S[k] = S[1] = A)
      next[j]= next[4] = k+1 = 2
    3. j = 5, k = next[j-1] = next[4] = 2,
      (S[j-1] = S[4] = B) == (S[k] = S[2] = B)
      next[j]= next[5] = k+1 = 3
    4. j = 6, k = next[j-1] = next[5] = 3,
      (S[j-1] = S[5] = A) == (S[k] = S[3] = A)
      next[j]= next[6] = k+1 = 4
    5. j = 7, k = next[j-1] = next[6] = 4,
      (S[j-1] = S[6] = B) == (S[k] = S[4] = B)
      next[j]= next[7] = k+1 = 5
    模式串 A B A B A B B
    j 1 2 3 4 5 6 7
    next 0 1 1 2 3 4 5
    void getNext(chat T[], int next[]) {
    	int i = 1;
    	next[1] = 0;
    	int j = 0;
    	while (i < T.length()) {
    		if (j == 0 || T[i] == T[j]) {
    			++i; ++j;
    			next[i] = j;
    		} else {
    			j = next[j];
    		}
    	}
    }
    
    int KMP(char S[], char T[], int next[], int pos) {
    	//求T在S中pos位置后的位置
    	int i = pos;
    	int j= 1;
    	while ( i <= S.length() && j <= T.length()) {
    		if(j == 0 || S[i] == T[j]) {
    			++i;++j;
    		} else {
    			j = next[j];
    		}
    	}
    	if(j > T.length())
    		return i - T.length();
    	else
    		return 0;
    }
    

    KMP 匹配过程

    主串:S=‘abcabaaabaabcac’,子串:T=‘abaabcac’
    next数组:

    模式串 a b a a b c a c
    j 1 2 3 4 5 6 7 8
    next 0 1 1 2 2 3 1 2
    1. 初始化 i = 1,j = 1
      ↓i = 1
      abcabaaabaabcac
      abaabcac
      ↑j = 1
    2. 因为S[1] = T[1] ,所以i++, j++
      .↓i = 2
      abcabaaabaabcac
      abaabcac
      .↑j = 2
    3. 。。。
    4. 因为S[3] != T[3],则 j = next[j] = 1
      …↓i = 3
      abcabaaabaabcac
      …abaabcac
      …↑j = 1
    5. 因为S[3] != T[1],所以 j = next[j] = 0
      …↓i = 3
      abcabaaabaabcac
      …abaabcac
      .↑j = 0
      6.因为j=0,所以 j ++, i++
      –…↓i = 4
      abcabaaabaabcac
      –…abaabcac
      –…↑j = 1
      7.。。。
      继续按上述方法分情况操作,指导匹配完成或者主串达到尾部匹配失败结束。

    KMP 算法改进

    到目前为止我们明白kmp算法就是在匹配不成功时给我们一个重新开始匹配的位置,以减少比较次数,那看看这种情况

    模式串 A A A A A B
    j 1 2 3 4 5 6
    next 0 1 2 3 4 5

    如果在j=5是匹配不成功,next[5] = 4,但是S[5] = S[4],也就是算法给的这个位置还是不能成功匹配,并且next[4] = 3,next[3] = 2…,这样就要从j=5比较到j=1,但是完全没有必要,这样我们就多比了四次,怎么解决何种问题呢?
    其实也很简单,算法给我们的next值比不是最后我们想要的位置,也就是next不是最优,原因是前面有大量相同的元素,那么我们在得到算法给的next值时,应该再继续判断一步,这个next值对应的位置上的值和匹配失败处的值是否相同,如果不相同,则调到这个next值所在位置,如果相同,那么继续判断下一个next是否相等,依次...,所以我们来从新修改next值记为nextval

    模式串 A B A B A A B
    j 1 2 3 4 5 6 7
    next 0 1 1 2 3 4 2
    1. j=1, nextval[1] = 0;
    2. j=2, S[j] = S[2] = B != S[next[2]] = S[1] = A, nextval[2] = next[2] = 1
    3. j=3, S[j] = S[3] = A == S[next[3]] = S[1] = A, 此时先判断next[next[3]] 是否为0,由于next[next[3]]= 0,所以nextval[3] = 0
    4. j=4, S[j] = S[4] = B == S[next[4]] = S[2] = B, next[next[4]] != 0, 继续判断S[j] 是否等于S[next[next[4]]], 由于S[j] = S[4] = B ==S[next[next[4]]]= S[1],所以nextval[4] = next[next[4]] = 1
    5. j=5, S[5] = A == S[next[5]] = S[3] = A, next[next[5]] = 1,继续判断S[5] S[next[next[5]]] = S[1] = A, 继续判断,由于next[next[next[5]]]= 0,所以nextval[5]=0,
    6. j=6, S[6] = A != S[next[6]] = S[4] = B, nextval[6] = next[6] = 4
    7. j=7, S[7] = B == S[next[7]] = S[2] = B, next[next[7]] = 1 != 0,继续判断,S[7] = B != S[next[next[7]]] = A, nextval[7] = next[next[7]]=1
    模式串 A B A B A A B
    j 1 2 3 4 5 6 7
    next 0 1 1 2 3 4 2
    nextval 0 1 0 1 0 4 1
    展开全文
  • kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
  • kmp算法ppt

    2017-11-27 19:27:36
    kmp算法基础讲解,适于从零开始了解KMP算法的朋友。课程内容简单易懂。
  • KMP算法详解

    万次阅读 多人点赞 2013-09-24 00:02:35
    kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简单明了地将其讲清楚。在此,综合网上比较好的...

    kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简单明了地将其讲清楚。在此,综合网上比较好的几个博客(参见最后),尽自己的努力争取将kmp算法思想和实现讲清楚。

    kmp算法完成的任务是:给定两个字符串O和f,长度分别为n和m,判断f是否在O中出现,如果出现则返回出现的位置。常规方法是遍历a的每一个位置,然后从该位置开始和b进行匹配,但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理,使匹配的复杂度降为O(n+m)。

    kmp算法思想

    我们首先用一个图来描述kmp算法的思想。在字符串O中寻找f,当匹配到位置i时两个字符串不相等,这时我们需要将字符串f向前移动。常规方法是每次向前移动一位,但是它没有考虑前i-1位已经比较过这个事实,所以效率不高。事实上,如果我们提前计算某些信息,就有可能一次前移多位。假设我们根据已经获得的信息知道可以前移k位,我们分析移位前后的f有什么特点。我们可以得到如下的结论:

    • A段字符串是f的一个前缀。
    • B段字符串是f的一个后缀。
    • A段字符串和B段字符串相等。

    所以前移k位之后,可以继续比较位置i的前提是f的前i-1个位置满足:长度为i-k-1的前缀A和后缀B相同。只有这样,我们才可以前移k位后从新的位置继续比较。


    所以kmp算法的核心即是计算字符串f每一个位置之前的字符串的前缀和后缀公共部分的最大长度(不包括字符串本身,否则最大长度始终是字符串本身)。获得f每一个位置的最大公共长度之后,就可以利用该最大公共长度快速和字符串O比较。当每次比较到两个字符串的字符不同时,我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位,接着继续比较下一个位置。事实上,字符串f的前移只是概念上的前移,只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。


    next数组计算

    理解了kmp算法的基本原理,下一步就是要获得字符串f每一个位置的最大公共长度。这个最大公共长度在算法导论里面被记为next数组。在这里要注意一点,next数组表示的是长度,下标从1开始;但是在遍历原字符串时,下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i],分别表示长度为1到i的字符串的前缀和后缀最大公共长度,现在要求next[i+1]。由上图我们可以看到,如果位置i和位置next[i]处的两个字符相同(下标从零开始),则next[i+1]等于next[i]加1。如果两个位置的字符不相同,我们可以将长度为next[i]的字符串继续分割,获得其最大公共长度next[next[i]],然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造,如果位置next[next[i]]和位置i的字符相同,则next[i+1]就等于next[next[i]]加1。如果不相等,就可以继续分割长度为next[next[i]]的字符串,直到字符串长度为0为止。由此我们可以写出求next数组的代码(java版):

    public int[] getNext(String b)
    {
    	int len=b.length();
    	int j=0;
    		
    	int next[]=new int[len+1];//next表示长度为i的字符串前缀和后缀的最长公共部分,从1开始
    	next[0]=next[1]=0;
    		
    	for(int i=1;i<len;i++)//i表示字符串的下标,从0开始
    	{//j在每次循环开始都表示next[i]的值,同时也表示需要比较的下一个位置
    		while(j>0&&b.charAt(i)!=b.charAt(j))j=next[j];
    		if(b.charAt(i)==b.charAt(j))j++;
    		next[i+1]=j;
    	}
    		
    	return next;
    }

    上述代码需要注意的问题是,我们求取的next数组表示长度为1到m的字符串f前缀的最大公共长度,所以需要多分配一个空间。而在遍历字符串f的时候,还是从下标0开始(位置0和1的next值为0,所以放在循环外面),到m-1为止。代码的结构和上面的讲解一致,都是利用前面的next值去求下一个next值。

    字符串匹配

    计算完成next数组之后,我们就可以利用next数组在字符串O中寻找字符串f的出现位置。匹配的代码和求next数组的代码非常相似,因为匹配的过程和求next数组的过程其实是一样的。假设现在字符串f的前i个位置都和从某个位置开始的字符串O匹配,现在比较第i+1个位置。如果第i+1个位置相同,接着比较第i+2个位置;如果第i+1个位置不同,则出现不匹配,我们依旧要将长度为i的字符串分割,获得其最大公共长度next[i],然后从next[i]继续比较两个字符串。这个过程和求next数组一致,所以可以匹配代码如下(java版):

    public void search(String original, String find, int next[]) {
    	int j = 0;
    	for (int i = 0; i < original.length(); i++) {
    		while (j > 0 && original.charAt(i) != find.charAt(j))
    			j = next[j];
    		if (original.charAt(i) == find.charAt(j))
    			j++;
    		if (j == find.length()) {
    			System.out.println("find at position " + (i - j));
    			System.out.println(original.subSequence(i - j + 1, i + 1));
    			j = next[j];
    		}
    	}
    }

    上述代码需要注意的一点是,每次我们得到一个匹配之后都要对j重新赋值。

    复杂度

    kmp算法的复杂度是O(n+m),可以采用均摊分析来解答,具体可参考算法导论。

    参考资料

    1.     kmp算法小结

    2.     kmp算法详解

    3.     kmp算法

    4.     kmp算法的理解与实现

    开源实现

    如果大家想实际用该算法,给大家提供一个实例:java记事本

    PS:

    最后再给大家补几个图,希望有助于大家理解。


    科赫曲线


    自身结构重复展开

    展开全文
  • KMP

    千次阅读 2017-01-15 17:33:12
    KMP

    ···············································这是一个叫前言的东西·············································
    很久以前就知道有一个叫KMP(看毛片)的恶心算法了,但在学之前真心不知道这么恶心直到……(牛犇不要吐槽蒟蒻)
    下面是一个自己对KMP的小总结,学得不久,可能不全面
    ············································这是前言和正文的分界线··············································

    一、一点和字符串有关的东西
    ······说KMP之前先来看看字符串吧……
    先来个例子:S = abbabbb
    1、子串:串中任意个连续的字符组成的子序列称为该串的子串(完全可以理解为数学中的子集);
    如:S的子串有ab abb abbb ……等;
    2、前缀:包括串中首字母的子串;
    如:S的前缀有a ab abb abba abbab abbabb abbabbb;
    3、后缀:包括串中尾字符的子串;
    如:S的后缀有b bb bbb abbb babbb bbabbb abbabbb;

    二、NEXT数组
    1、······铺垫了那么多看个题目先……
    POJ 2752 Seek the Name, Seek the Fame给定一字符串S,求S中既是前缀又是后缀的子串。 ——我还没有写就不放代码了,next数组就可以了······似乎
    *既是前缀又是后缀:即出现在前缀列又出现在后缀列的子串;
    如:S = abbabbb 中 ab就是既是前缀又是后缀
    2、next数组
    对于字符串T,next[i]表示对于前缀S1…i 这个字符串,最长的一个与其等长前缀相等的后缀的长度(完全相同的(长度相等,每一位都相同)前缀、后缀的最大长度 (不考虑字符串本身))。
    如:字符串 abbabbb中
    next[5]:
    abbab 前缀:a ab abb abba
    后缀:b ab bab bbab
    即为ab长度–> next[5] = 2;
    3、代码实现
    这里写图片描述

    ①nxt[1] = 0 ;
    for (int i = 2; i <= len; ++i)//t[i]为字符串第i位字符,nxt即为next数组/
    {
    int j = nxt[i - 1];
    while(j > 0 && t[i] != t[j + 1]) j = nxt[j];
    if (t[i] == t[j + 1]) j++;
    nxt[i] = j;
    }
    ②void next(string T, int &next[])
    {
    int i = 1; next[1] = 0;j = 0;
    while (i < T[0]){
    if (j == 0 || T[i] == T[j]){
    ++i;++j;
    if (T[i] !=  T[j])    next[i] = j;
    else next[i] = next[j]; 
    }
    else j = next[j];
    }
    }

    三、KMP算法
    1、上题目 POJ 3461 Oulipo给定字符串S和T,求T在S中的出现次数。
    这里写图片描述
    2、KMP代码

    while(p<=lens){
      if(s[p]==t[j]){
      ++p,++j;
      if(j>lent){
      puti(p-j+1);
      putchar('\n');
      if(j!=1)j=ne[j-1]+1;
      else p++;
      }
      }
      else{
      if(j!=1)j=ne[j-1]+1;
      else p++;
      }
    }  

    3、AK大神YWJ的KMP算法

    int kmp()
    {
      int ans=0,j=0;
      for(int i=1; i<=l1; i++)
      {
      while(j&&b[j+1]!=a[i]) j=nxt[j];
      if(b[j+1]==a[i]) j++;
      if(j>=l2) ans++,j=nxt[j];
      }
      return ans;
    }

    4、再放一种KMP函数(有注释)

    int Index(SString S, SString T, int pos){
    /返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。
    其中,T非空,1 <= pos <= StrLength(S)。/
    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;
    }//Index/

    四、KMP的练习

    • hihoCoder 1015
      • 一道简单的KMP裸题
      • 然后是对自己的一点小提醒
        1、next数组对应的是模式串
        2、注意模式串和原串都要从下标’1’开始
        3、本题的ans记录的是模式串出现的次数,可根据需要更改
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    using namespace std;
    
    int n;
    char a[1000100], b[10100];
    int nxt[1000100];
    int la, lb;
    
    int main(){
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i){
            cin >> b >> a;
            la = strlen(a), lb = strlen(b);
            for (int j = lb; j > 0; j--) b[j] = b[j - 1];
            for (int j = la; j > 0; j--) a[j] = a[j - 1];
            nxt[1] = 0;
            for (int j = 2; j <= lb; ++j){
                int p =nxt[j - 1];
                while (p > 0 && b[p + 1] != b[j]) p = nxt[p];
                if(b[p + 1] == b[j]) p++;
                nxt[j] = p;
            }
            int ans = 0, p = 0;
            for (int j = 1; j <= la; ++j){
                while (p && b[p + 1] != a[j]) p = nxt[p];
                if (b[p + 1] == a[j]) p++;
                if (p >= lb) ans++, p = nxt[p];
            }
            printf("%d\n", ans);
            memset(a, '0', sizeof(a));
            memset(b, '0', sizeof(b));
        }
        return 0;
    }
    • CJOJ P2566 字符串最大值
      • 一个对next数组使用的题目,挺简单的
      • 一点点提示和反省
        1、如abababa中,next[7]的值是由ababa ba 及 ab ababa决定的!!!(一下午都把next数组当成回文数了……)
        2、这道题比对时应倒着来(手玩一下吧)
        3、最后别忘了乘以长度
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    using namespace std;
    
    char t[1000100];
    int nxt[1000100];
    int ans[1000100];
    int maxx = 0;
    
    int main(){
        scanf("%s", t + 1);
        nxt[1] = 0;
        int len = strlen(t + 1);
        for (int i = 2; i <= len; i++){
            int j = nxt[i - 1];
            while (j && t[j + 1] != t[i]) j = nxt[j];
            if (t[j + 1] == t[i]) nxt[i] = j + 1;
        }
        for (int i = len; i >= 1; --i) ans[i]++, ans[nxt[i]] += ans[i];
        for (int i = 1; i <= len; ++i) maxx = max(maxx, ans[i] * i);
        printf("%d\n", maxx);
        return 0;
    }

    五、总结未做题

    1. hihocoder 1084 : 扩展KMP
    2. POJ 2752 Seek the Name, Seek the Fame
    3. POJ 3461 Oulipo

    —— CYCKCN

    展开全文
  • KMP算法实例

    2012-06-14 10:28:31
    初学者对于KMP算法都很头疼,自己写的KMP算法实例,自己也是一个新手,希望能提供帮助!
  • 算法 kmp算法

    2018-04-25 20:31:06
    kmp算法是改进后的字符匹配算法,它与bf算法的区别是,每次从串与主串匹配失败后,从串与主串匹配的位置不同。下面具体说下这两种算法的区别:主串:BABCDABABCDABCED从串:ABCDABCEDBF算法:第一步:...
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • kmp算法

    千次阅读 多人点赞 2014-05-29 15:52:29
    关于kmp算法,相信大家都不会陌生。但是,对于我自己而言,da'bu'fen
  • BF算法、KMP算法、改进的KMP算法

    千次阅读 2018-08-14 17:48:43
    BF算法、KMP算法、改进的KMP算法,以上几种算法都是模式匹配算法,即找模式串在主串中第一次出现的位置。 BF算法: 如上图所示 主串:”abcaba” 子串:”aba” 思路:从主串第一个开始和子串第一个匹配,如果...
  • KMP算法及改进KMP算法实现

    千次阅读 2017-02-14 12:28:42
    *描述:KMP算法以及改进后的KMP算法实现 */ #include #include #define MaxSize 100 typedef struct { char data[MaxSize]; //定义可容纳MaxSize个字符的空间 int length; //标记当前实际串长 } ...
  • KMP算法——很详细的讲解

    万次阅读 多人点赞 2018-09-09 10:52:23
    KMP算法(研究总结,字符串) KMP算法(研究总结,字符串) 前段时间学习KMP算法,感觉有些复杂,不过好歹是弄懂啦,简单地记录一下,方便以后自己回忆。 引入 首先我们来看一个例子,现在有两个字符串A和B,...
  • KMP算法最浅显理解——一看就明白

    万次阅读 多人点赞 2017-02-07 17:41:08
    KMP算法看懂了觉得特别简单,思路很简单,看不懂之前,查各种资料,看的稀里糊涂,即使网上最简单的解释,依然看的稀里糊涂。 我花了半天时间,争取用最短的篇幅大致搞明白这玩意到底是啥。 这里不扯概念,只讲...
  • Manacher算法、KMP算法

    千次阅读 2015-12-18 17:19:17
    一、Manancher算法Manacher算法用于查找子串中的回文,算法维持的三个变量十分重要pArr(下标所在位置字符回文长度)、index(回文中心)、pR(回文半径),这种算法比其他算法效率高的原因在于,它可以利用前面已...
  • 一步一步带你用Python实现KMP算法
  • KMP算法—终于全部弄懂了

    万次阅读 多人点赞 2019-03-22 21:00:45
    详细讲解KMP算法,并对难点 k=next[k] 这条语句重点描述
  • KMP算法简介

    千次阅读 2017-03-25 09:26:06
    KMP算法如果理解原理的话,其实很简单。 KMP算法简介 这里根据自己的理解简单介绍下。 KMP算法的名称由三位发明者(Knuth、Morris、Pratt)的首字母组成,又称字符串查找算法。 ...
  • KMP算法笔记

    2018-09-18 11:31:03
    KMP算法经典高效的字符串匹配算法。腾讯2018年算法岗笔试题的第一题考了KMP算法的应用,没掌握KMP的在复杂度上肯定是通过不了的。也是因为腾讯笔试题,我才打算好好了解一下KMP算法。 网上有很多优秀的关于KMP算法...

空空如也

1 2 3 4 5 ... 20
收藏数 36,114
精华内容 14,445
关键字:

kmp