找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1693|回复: 1
收起左侧

[基础刷题题目讨论] [题解]Iteration of String

[复制链接]
发表于 12-17-2014 02:13 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-17-2014 02:14 PM 编辑

问题原帖

问一个字符串是不是周期串。

这是个简单题。最早见这个题在ZOJ上。

其实这个题考察的是对KMP的理解。 可以证明如果原始串是个周期串的话,
(1) next[n]  = 总长度 - 一个周期的长度。  首先next的意义是非自身的、前一位为最后一个字符的最长的后缀串等于前缀串的长度。
例如 abcabcabc   next[n] (注意这个值已经超过字符串边界) = 6。 这是因为前6个字符和最后6个字符都是abc
(2) n % (n - next[n]) == 0 表示最后一个串恰好是一个周期。
例如abcabcab  ,这个最后一个周期不完整,就不符合条件。因为next[n] = 5, n = 9...


所以就是把next数组求出来,看一下就好了……因为KMP是线性的……所以算法是线性的。

本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 2-17-2015 04:58 AM | 显示全部楼层
next就是求最长真后缀是前缀的字符串,好拗口。。

还有个直白点的方法,把字符串重叠一次,然后再用原字符串进行匹配,如果能在除首位的地方进行匹配,那么就是周期串,第一次匹配到的地方就是最小周期~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表