leetcode-day08-字符串

重复的子字符串


题解:

首先找到 s 的最短重复子串 t,即 t 是 s 的一个前缀,并且 s 可以由 t 重复若干次得到。具体方法是从字符串的中间位置开始,逐步缩小范围,直到找到一个长度为 len(s)//2 或更短的子串 t,使得 s 可以由 t 重复若干次得到。如果不存在这样的子串,则 s 不可能由其子串重复多次构成。

检查 s 是否可以由 t 重复若干次得到。具体方法是判断 len(s) 是否是 len(t) 的倍数,如果不是则 s 不可能由 t 重复若干次得到;否则将 s 分解为 len(t) 个子串,检查每个子串是否等于 t。如果所有子串都等于 t,则 s 可以由 t 重复若干次得到;否则 s 不可以由其子串重复多次构成。

代码:

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容