4.3知识精炼（一）高清版本.pdf

知识精炼（一）

主讲人：邓哲也

HDU4333RevolvingDigits

给一个L位数的正整数N，每次可以把这个数的最后一位

移到最前面来，得到一个新的数。

总共最多可以得到n个数，重复的只算一次。

问这些数中，等于n的，小于n的，大于n的数分别有几

个。

L≤105

样例：

341（答案：111）

HDU4333RevolvingDigits

我们只需要把这个数复制两遍，然后只考虑长度为n的子

串。

这些子串就是移动过程中产生的数。

如何和原数N做比较呢？

HDU4333RevolvingDigits

假设现在的数是S[i..i+L-1]

N是S[1..L]

我们只要求出他们的最长公共前缀x，如果x=n说明这

两个数相等。

否则，比较S[x]和S[i+x-1]的大小，就可以确定他们的

大小关系。

求x，就是扩展KMP中的Z算法。x=min(n,Z[i])

HDU4333RevolvingDigits

最后一步去重。

对N跑一次KMP

如果L-next[L]是L的约数，那么L-next[L]是N的最

小循环节。

否则N的最小循环节是L。

对循环节内的情况枚举一遍即可。

时间复杂度O(L)

POJ3376FindingPalindromes

给你n个字符串m[1],m[2],…,m[n]。

求S=m[i]m[j]（1=i,j=n）是回文串的数量。

n个字符串的长度之和不超过2·106

样例输入：

3

a

ab

ba

答案：5（aa,aba,aba,abba,baab)

POJ3376FindingPalindromes

考虑什么情况下i和j拼起来会是回文串。

i的长度和j的长度相等

必须满足i是j的反串。

i的长度小于j：

i必须是j的反串的前缀，且j的反串剩下的部分

是回文串。

i的长度大于j：

与上一种情况相反。

POJ3376FindingPalindromes

把n个串插入Trie。

每个节点维护两个值：

value1：到当前节点的字符串个数

value2：当前节点后面的回文子串的个数

POJ3376FindingPalindromes

现在用每个字符串的反串去Trie上查找。

如果构成回文串：

这个反串是其他串的前缀，那么答案要加上value2

这个反串的前缀是某些字符串，且反串剩下的后缀是

回文串，答案要加上value1

POJ3376FindingPalindromes

留下的问题就是一个字符串的所有后缀中，哪些是回文串。

对于串S，我们先求出正串S对反串T的extend[i]

那么对于每个i，如果S[i..n]和T的最长公共前缀等于

S[i..n]的长度，说明S[i..n]是一个回文串。

因此整道题就在线性的时间复杂度内解决了。

下节课再见