题目描述输入格式无 输出格式无 题意翻译题意描述对于给定字符串S的每个前缀,我们想知道它是否为周期串。也就还是说,它是否为某一字符串重复连接而成(必须至少重复2次)(即循环节)。 输入多组数据。每组数据,第一行一个数字表示长度,第二行一个字符串S。 输出输出前缀长度与循环节数量。 说明字符串长度不超过1000000,仅由小写字母组成。 对于每个前缀,只要输出长度最小的循环节 输入输出样例无 一道KMP算法的练手好题。 大体的题目大意是这样的: 题目大意:如果一个字符串S是由一个字符串T重复K次形成的,则称T是S的循环元。使K最大的字符串T称为S的最小循环元,此时的K称为最大循环次数。 现给一个给定长度为N的字符串S,对S的每一个前缀S[1~i],如果它的最大循环次数大于1,则输出该前缀的最小循环元长度和最大循环次数。 题解:一道KMP算法的题目,如果对KMP算法还是没有什么深刻的理解或者还没学KMP算法的,请移步我的这篇博客,讲解还算详细: 一开始拿到题没什么思路(我还是太菜了) 后来发现,对给出的串\(S\)自匹配求出\(nxt\)数组之后,对于每一个\(i\),一定会有这么一个结论: 那么,既然这两个东西是相等的,那么在对这个子串进行匹配的时候,这个循环节长度就应该是\(i-nxt[i]\),然后循环次数当然就是\(i/(i-nxt[i])\),当然,前提需要是\(i\%(i-nxt[i])==0\)。 代码如下: 来源:https://www./content-4-579251.html
|
|