【题目链接】

点击打开链接

【算法】

KMP

如果字符串中存在循环节,则next[len] = (循环节个数 - 1) * 循环节长度

循环节个数 = len / (len - next[len])

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXL 10000010 int len;
char s[MAXL];
int next[MAXL]; template <typename T> inline void read(T &x) {
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
} inline void getnext() {
int i,pos;
next[] = ;
for (i = ; i <= len; i++) {
pos = next[i-];
while (pos > && s[pos+] != s[i]) pos = next[pos];
if (s[i] == s[pos+]) next[i] = pos + ;
else next[i] = ;
}
} int main() { while (true) {
scanf("%s",s+);
if (s[] == '.') return ;
len = strlen(s+);
getnext();
if (len % (len - next[len]) == ) writeln(len/(len-next[len]));
else writeln();
} return ; }

最新文章

  1. Firefox 插件 FlashGot 创建 Axel 下载任务
  2. System.Security.SecurityException The source was not found, but some or all event logs could not be searched.Inaccessible logs Security.
  3. Android自定义View滑动事件处理总结
  4. 什么是Mbps、Kbps、bps、kb、mb及其换算和区别
  5. WinJs项目介绍
  6. KVC实现原理简介
  7. Stay教你程序员泡妞攻略
  8. Nginx目录别名(Alias)支持PHP的配置
  9. &lt;转&gt;linux进程间通信&lt;一&gt;
  10. eclipse中加放js文件报js语法错误解决办法
  11. Android 如何在Java代码中手动设置控件的marginleft
  12. Delphi中使用TXMLDocument控件应注意的问题 转
  13. VS2013和VS2015中MVC 区域路由匹配顺序相反
  14. thymeleaf模板引擎入门
  15. java基础学习系列一
  16. Quikapp快应用开发入门
  17. [Python数据挖掘]第2章、Python数据分析简介
  18. R语言实战(三)——模拟随机游走数据
  19. 学习笔记之Sublime Text
  20. 使用IDEA进行Lua代码调试、自动提示、代码跳转、智能重命名

热门文章

  1. CF 2018 Battle of Brains GYM 102062 F
  2. Codeforces 86D Powerful array (莫队算法)
  3. gorm 结构体 预加载
  4. NSURLConnection和NSMutableURLRequest 实现同步、异步请求
  5. flask结合令牌桶算法实现上传和下载速度限制
  6. Cocos2d-x游戏《雷电大战》开源啦!要源代码要资源快快来~~
  7. Android中Intent具体解释(二)之使用Intent广播事件及Broadcast Receiver简单介绍
  8. Eureka vs Zookeeper
  9. Redis HyperLogLog及应用
  10. MYSQL强制使用索引和禁止使用索引