小衣同学的博客

形如[l1,l1+d1,l1+2*d1,...][l2,l2+d2,l2+2*d2,...],...,[lx,lx+dx,lx+2*dx,...]……所以考虑用总的[1,i]的b之和，减去已经没贡献的，也就是[x,i]与前缀的lcp小于i-x+1的，没贡献的x，一定会在某个x<=j<=i的位置变得没有贡献，只被减一遍之后，后面就不用减了。推导不难发现，满足[x,i]与[1,i-x+1]完全相同的x，是有贡献的x。根据题目要求的式子，假设当前匹配到了i，也就是从i-1转移到i的时候，

然后扫描线，每个i有一个[i,i+z[i]-1]的区间，在这个区间内以j结尾时，和前缀的lcp固定为[i,j]这个需要预处理mn[i][j]表示前i个字符出现j次时的结尾处的最小下标，没有的话就是n+1。然后[i,i+z[i]-1]的扫描线保证了以p结尾的一定是一个当前合法的A串，对于位置p，出现次数cnt，二分找到满足mn[x][cnt]<=p的最大x，长度x的前缀出现了cnt次，那么短于长度x的前缀一定出现了cnt次，对于大于一次的情况，先二分当前最大的可行长度x，对于每个i，先特判只出现一次的情况。

将s1扩展成原来的2倍之后（s1=s1+s1），与s2做扩展kmp即可。你可以自行选择一个k(0

题目bzoj3670对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]例如S为aaaaa，则num[4] = 2。这是因为S的前4个字符为aaaa，其中a和aa都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，num[1] = 0,num[2] = num[3] = 1,num[5

题目假设有两个等长的串x和y，保证字符只包含‘a’-'f'的小写字母你可以每次选择两个字符，不妨设为'a'和'b'，把两个串中当前所有'a'都改成'b'计编辑距离为二者改成相同的串的最小修改次数，比如x串为abcd，而y串为ddcb，则编辑距离为2第一次可以把a改成b，有x串为bbcd，y串为ddcb第二次可以把b改成d，有x串为ddcd，y串也为ddcd现给出两个串S和T(|T|<=|S|<=125000)，对于S中每个长度为|T|的子串，输出其与T的编辑.

题目找出一个给定串的所有循环节，输出这个个数，和所有的前缀长度思路来源https://blog.csdn.net/weixin_41380961/article/details/80278317https://www.cnblogs.com/ikids/articles/4658884.html题解考察的是对next[]数组的理解令m=strlen(t)，则m-ne...

题意：找到最大的i，使存在j小于i，使串j不是串i的子串。题解：暴力KMP即可，毒瘤题。注意：①剪枝：若前串是后串的子串，后串不匹配则一定前不匹配；若后串匹配前串一定匹配。开个vis数组标记下，如果存在被后串匹配过的前串，跳过就可以了。②C语言strstr函数的应用，比KMP略快，卡时间过的毒瘤题。代码实现：#include&lt;iostream&gt;#incl...

题意问该串是最短循环节重复了几次而形成的串，输出这个次数。题解①kmp显然可做，求len-next[len]即循环节的长度，然后判断是否能被len整除即可。②后缀数组：枚举循环节长度i,i从1到len/2，如果长度为i，则循环节显然为0-(i-1)的子串先判断i是否能被len整除，再看suffix(0)与suffix(i)的最长公共前缀是否为len-i，其与next[len...

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...

It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:s: "abab...

题目大意：给你一个串（串长1e6），输出该串在前缀、后缀出现过，且在中间出现过至少一次的串的最大长度的值。题目思路：最长的可能就是r=next[m](m为该串的长度)，先判断一下是否可行，可行直接输出。                  否则记l=0,mid=(l+r)/2，mid为答案串的长度，二分查找长度。                  mid可行就用l保存下来，不可行就用r保...