exkmp专题

KMP,EXKMP 扩展KMP

EXKMP是KMP算法的一个扩展和加难,可以解决一些KMP无法解决的问题 先回顾一下KMP KMP KMP的关键是next数组 next[i]表示的是s[1~next[i]]=s[i-next[i]+1~i] 在进行字符串匹配时如将s和t匹配时 如果t[i+1]和s[j+1]不对时,可以将t[i+1]和s[next[j]+1]进行匹配,因为next数组满足上面的性质,可以保证s[1~n

bzoj3670 Noi2014动物园 - exkmp

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3670 题意:求出一个num数组一一对于字符串S的前i个字符构成的子串T,有字符串既是T的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作num[i]。求对1,000,000,007的取模 题解:不会kmp的我用exkmp做了。。求出的extend[]就是下面

hdu4333 Revolving Digits - exkmp

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4333 题意:多组数据,给一串数字,问每次旋转得到的数字串比原串小、等、大的数量。e.g.原串为"341",而3次旋转得到的数字串分别是:341、134、413。故答案输出1 1 1 题解:exkmp;题目中说的是能构成的不同的串,而当且仅当原串有循环节时所构成的串有重复(自己想想),所以先用nex

HDU3613 Best Reward - exkmp/Manacher

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3613 题意:多组数据,给定每个字母的价值和一个串S,要把这个串S分成两个串T1、T2,若某串T是回文串那么就能获得该串上字母的价值,否则可获得的价值为0,求最大价值 题解:RT 用exkmp或者马拉车搞一搞就好了 心得什么的:撒比的我想着用exkmp搞,练习一下,结果..一搞就搞了半个世纪qwq