revolving专题

HDU 4333 Revolving Digits 扩展KMP

题目来源:HDU 4333 Revolving Digits 题意:求一个数字循环移动后有多少个不同的小于 等于 大于的数字 思路:扩展KMP求出S[i..j]等于S[0..j-i]的最长前缀 判断 next[i] 大于等于n就是相同 小于n判断S[next[i]]和S[next[i]+i]的大小 next数组的含义就是S字符串以i开始的和S本身(以0开始)的最长公共前缀 把题目输入的复制一

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

HDU-4333-Revolving Digits(扩展KMP)

CSDN 题目链接 题意: 给你一个字符串,你可以将该字符串的任意长度后缀截取下来然后接到最前面,让你统计所有新串中有多少种字典序小于、等于、大于原串。 题解: 首先我们将原串扩展成两倍,算一遍扩展KMP(自匹配),时间复杂度O(n)。这样一来,我们就得到了eKMP[i],eKMP[i]代表s[i…len-1]与s的最长公共子串。为了避免重复子串重复计数,我们先求出s的最小循环节:然