4.4知识精炼（二）高清版本.pdf

知识精炼（二）

主讲人：邓哲也

HDU4763ThemeSection

给你一个字符串S。

请你把这个S划分成EAEBE的形式。

其中A和B可以包含任意个（可以是0个）字符。

求E的最大长度。

字符串的长度之和不会超过106

HDU4763ThemeSection

观察EAEBE。

首先要保证E既是S的前缀又是S的后缀。

且去除掉前缀E和后缀E之后，中间剩下的还要出现一次E。

对S跑一次扩展KMP中的Z算法。

如果i+Z[i]-1==n，就说明S[i..n]可以作为E。

那么就要求在S[Z[i]+1..i-Z[i]]中，还得存在一个j满足Z[j]≥Z[i]

HDU4763ThemeSection

问题变成了先找i+Z[i]-1=n的i

然后在[Z[i]+1..i-Z[i]]中，查询Z的最大值，如果比

Z[i]大，那么就可以把Z[i]作为答案。

最后取最大值即可。

查询区间最大值我们可以用线段树/ST表来维护。

最后的时间复杂度都是O(nlogn)

HDU6153ASecret

给定两个字符串S和T。对于T的每个后缀，L[i]表示

后缀的长度，N[i]表示这个后缀在S中出现的次数。

求∑L[i]N[i]

|S|,|T|≤106

例如S=abababab,T=aba

答案=3*3+3*2+4*1=19

HDU6153ASecret

把T反转一下，这样后缀就变成了前缀。

如何求T的每个前缀在S中出现了几次？

运用extend数组来帮忙。

比如extend[i]=4

说明S[i..i+3]=T[1..4]，那么T的前四个前缀出现的

次数就都会加一。

因此每次只要对[1,extend[i]]这个区间加一即可。

HDU6153ASecret

这道题求的是∑L[i]N[i]

因此我们可以算出次数再最后统计乘积之和。

也可以对于extend[i]，直接把1+2+3+…+extend[i]计入

答案。

时间复杂度O(n)

下节课再见