poj 2406 Power Strings (后缀数组||kmp)

poj 2406

题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的,
求 R 的最大值

思路:论文题.

转载论文中的题解:

做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候,
先看字符串 L 的长度能否被 k 整除,再看 suffix(1)和 suffix(k+1)的最长公共
前缀是否等于 n-k。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ
问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到
height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n)

最关键的在加黑的那句话:看 suffix(1)和 suffix(k+1)的最长公共
前缀是否等于 n-k

why???

转载一段证明:

为什么这样就行了呢?这要充分考虑到后缀的性质。当lcp1k+1=n-k时,后缀k+1是后缀1(即整个字符串)的一个前缀。(因为后缀k+1的长度为n-k)那么,后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。而后缀1的第k+1..2k个字符,又相当于后缀k+1的前k个字符,所以与后缀1的前k个字符对应相同,且和后缀kk+1..2k又对应相同。依次类推,只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值,就可以得到n/k的最大值了。

虽然这道题不适合用后缀数组做,倍增会tle,dc3也是卡时间才能过,但是接触到了一个想法.

要看一个字符串s能否由一个较小的长度为k的字符串t重复若干次得到,除了要整除以外,

gengxin判断suffix(1)和 suffix(k+1)的最长公共前缀是否等于 n-k即可.

 

下面是用倍增写的tle了的代码,价值在于那段没有用rmq,而是o(n)更新height数组到height[rk[0]]之间的最小值要怎么写.

 

 

 

 

 

kmp的思路:

KMP中的get_next(),或者get_nextval(),对next数组的应用。next[len]是最后一个字符跳的步长,如果他有相同字符串,则该串长度是len-next[len](这点我还在想要怎么证明!)…如果整个长度len能分解成x个这种串(能整除),就得到ans了。否则不能分解。只能是由他自己组成串,长度为1。

这道题用kmp非常块…

但是其实…………

其实………..

 

 

 

 

其实我不会kmp………………….

搞完后缀数组去学下.

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz