KMP的Next数组:模式串的前缀与后缀的“相交”长度 KMP算法步骤: 1.先算next数组 2.若失配(此时模式串下标为j),利用Next数组求出失配后滑动的新位置 a.Next[j] \geq 0,则模式串右移 j-Next[j] 位 b.Next[j] = -1,则模式串右移 j+1 位 初始 i = 0, j = -1,Next[ 0 ] = -1(为了后面计算方便); Step1: 由于j == -1,i&j++,且Next[i] = j,即Next[1] = 0; 此时 i = 1

Period Problem Description For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to

这题可以用后缀数组,KMP方法做 后缀数组做法开始想不出来,看的题解,方法是枚举串长len的约数k,看lcp(suffix(0), suffix(k))的长度是否为n- k ,若为真则len / k即为结果. 若lcp(suffix(0), suffix(k))的长度为n- k,则将串每k位分成一段,则第1段与第2段可匹配,又可推得第2段与第3段可匹配……一直递归下去,可知每k位都是相同的,画图可看出匹配过程类似于蛇形. 用倍增算法超时,用dc3算法2.5秒勉强过. #include<cstdi

题目链接:http://poj.org/problem?id=2406 题意:给定一个字符串,求由一个子串循环n次后可得到原串,输出n[即输出字符串的最大循环次数] 思路一:KMP求最小循环机,然后就能求出循环次数. #define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<str

KMP算法的next[]数组通俗解释   我们在一个母字符串中查找一个子字符串有很多方法.KMP是一种最常见的改进算法,它可以在匹配过程中失配的情况下,有效地多往后面跳几个字符,加快匹配速度. 当然我们可以看到这个算法针对的是子串有对称属性,如果有对称属性,那么就需要向前查找是否有可以再次匹配的内容. 在KMP算法中有个数组,叫做前缀数组,也有的叫next数组,每一个子串有一个固定的next数组,它记录着字符串匹配过程中失配情况下可以向前多跳几个字符,当然它描述的也是子串的对称程度,程度越高,值

Description Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Building Masters (IBM), which has recently asked

题意 给出一个长度为n的环状由小写字母组成的序列,请找出从何处断开,顺时针还是逆时针,使得字典序最大.如果两个字符串的字典序一样大,那么它会选择下下标最小的那个.如果某个点顺时针逆时针产生的字典序大小相同,那么优先选择顺时针的. 这个题用最大表示法+KMP很容易解决.因为最大表示法找到的是下表最小的那个字典序最大的字符串,所以正向的时候最大表示法找出来的就直接是答案,关键是逆时针的时候.我们将字符串翻转以后用最大表示法找到那个字符串s2,然后用KMP算法在翻转*2后的串中找出最后面的那个s2,这

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defin

题面 传送门 思路 首先,这题最好的一个地方,在于它给出的关于$next$的讲解实在是妙极......甚至可以说我的kmp是过了这道题以后才脱胎换骨的 然后是正文: 如何求$num$数组? 这道题的输入有1e6个字符,显然需要$O\left(n\right)$左右级别的算法来解 先看到$num$的定义:不互相重叠的公共前后缀个数 这说明什么? 说明$num$不同于$next$记录的是一个最大值,它记录的是一个和值 而这个和值,是可以推出来的 考虑一个前缀$i$的$next[i]$,它长这样: 其

题目链接 Description 给出\(n\)个序列.找出这\(n\)个序列的最长相同子串. 在这里,相同定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串. 思路 参考:hzwer. 法一:kmp 在第一个串中枚举答案串的开头位置,与其余\(n-1\)个串做\(kmp\). 法二:后缀数组 将\(n\)个串拼接起来.二分答案\(len\),将\(height\)分组,\(check\)是否有一组个数\(\geq len\)且落在\(n\)个不同的串中. 注意:\(n\)个串

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defin

题目链接:https://vjudge.net/problem/POJ-2752 Seek the Name, Seek the Fame Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 21220   Accepted: 11065 Description The little cat is so famous, that many couples tramp over hill and dale to Byteland

题目大意 题目看样例也能猜到就是输出最短的循环串. 吐槽 明明是div3第一题为啥子还会用到kmp的知识? 解法 这个题仔细看发现是求最长可去除的后缀,也就是说去除跟下一个相同的字符串还能连接起来.这个不就是next数组的功能吗?最长公共前后缀. 公式:len-next[len] 我们把前k-1个字符串只输出前面的部分最后加上一个完整的字符串即可 完整代码 #include <bits/stdc++.h> using namespace std; char a[500]; int nex[50

题意:让你找最小重复串的个数 加深KMP中对next数组的理解 #include <cstdio> #include <cstring> using namespace std; int next[1000500],slen; char s[1000500]; void get_next(){ int i=1,j=0; next[1]=0; while(i<=slen){ if(j==0||s[i]==s[j]) next[++i]=++j; else j=next[j];

Cyclic Nacklace Problem Description CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the

题意:求字符串s的所有前缀出现次数之和. http://www.cnblogs.com/jklongint/p/4446117.html 思路:用kmp做,简单且效率高.以前缀结尾的位置分类,令dp[i]为以结尾位置在i的前缀数量,那么dp[i] = cnt(j)(j~i是前缀),而由kmp的next函数的转移性质,可得如下递推方程:dp[i] = dp[next[i]] + 1,把这个递推式不断展开,也就是i = next[i]不断迭代,那么+1的个数就是dp[i] = cnt(j)(j~i是

题意:       给n个串(n>=2&&n<=10),每个串长度都是60,然后问所有串的最长公共子串,如果答案不唯一输出字典序最小的. 思路:直接暴力,枚举+KMP,后缀数组 枚举+KMP #include<stdio.h> #include<string.h> char a[12][62] ,b[62]; int next[62]; void Get_Next(char b[]) { int m = strlen(b); int j = 0 ,k =

题意:给一个字符串S,判断在什么下标的时候,前缀和后缀相等,输出前缀和后缀相等的点. 分析:next数组的一种很巧妙的用法 next数组表示的意义是当前下标前面k字符和开头的前面k个字符相等 所以就会有xy=ab(用xy表示x - y的这一段),则next[b]=y,那么下次就从y这个位置开始匹配 如果xk=wy,因为xy=ab,故wy=lb,所以xk=lb,就得到了前缀和后缀相等. 详细见:http://www.mamicode.com/info-detail-977140.html 代码:

input n 2<=n<=1000000 长度为n的字符串,只含小写字母 output Test case #cas 长度为i时的最小循环串 循环次数(>1) 若没有则不输出 做法:若next数组是连续的整数且next[i]+1是错位部分长度的倍数,则必有循环出现,且循环次数为(i+1)/错位部分长度 #include <cstdio> #include <queue> #include <cstring> #include <iostream

性质:如果len%(len-next[len-1])==0,则字符串中必存在最小循环节,且循环次数即为len/(len-next[len-1]); 证明:在前len个字符组成的字符串,存在最小循环节k,那么next[len-1]=len-k;(为什么呐?因为next数组的定义就是最大前后缀相同的子串的长度,len的总长度减去最小循环节,比如有3个循环节,减去一个剩下两个,就是最大循环节)那么循环次数就是len/(len-next[len-1]);因为len-next[len-1]=k;所以得出公

题面 传送门 思路 先把题面转成人话: 对于给定串的每个前缀i,求最长的,使这个字符串重复两边能覆盖原前缀i的前缀(就是前缀i的一个前缀),求所有的这些"前缀的前缀"的长度和 利用$next$的性质:前缀$i$的长度为$next[i]$的前缀和后缀是相等的 这说明:如果有i一个公共前后缀长度为j,那么这个前缀i就有一个周期为i-j 见下图 显然图中蓝色线段是黑色线段的一个周期 那么接下来的问题就容易了: 先求出$next$数组 对于每个前缀$i$,令$j=i$,然后在$j>0$的