本文主要是介绍POJ - 2406 Power Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题面
http://poj.org/problem?id=2406
2.题意
已知一个字符串s是由某个串t经过n重复形成的
现在给你s希望你求出n最大可以是多少
3.思路
这道题用后缀数组的倍增算法写居然会超时，不得套了一个DC3算法，总算过了。
然而即使使用了DC3算法程序的运行时间依旧高达2.5ms
正解应该是kmp算法，没关系，有空我再补上。
用后缀数组有两种写法
第一种是罗穗蹇在他的pdf中介绍的，建立好height数组后，枚举t的长度k，k能整除s的长度那是必须的，除此意外要求Suffix(0+k)与Suffix(0)的最长公共前缀长度为n-k，因为从小到大枚举k所以找到一个合法的k之后就可以直接输出结果了
第二种和第一种差不多，慢了200+ms，没什么好说的，直接贴在下面了
4.代码
/*****************************************************************> File Name: Cpp_Acm.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2016年07月30日 星期六 21时03分33秒
*****************************************************这篇关于POJ - 2406 Power Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
