KMP求循环节。
 
  循环节推导的证明相当的好,这题是很裸的套算法的题。
代码如下:
 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int N = ;
char buf[N];
int next[N]; void getNext(char *str) {
char *si = str;
int *ni = next;
int j = *next = -;
while (*si) {
while (j > - && *si != *(str + j)) j = *(next + j);
si++, ni++, j++;
// if (*si == *(str + j)) *ni = *(next + j);
// else *ni = j;
*ni = j;
}
} int minMaxExp(char *s, bool mini) {
int i = , j = , k = , t;
int len = strlen(s);
while (i < len && j < len && k < len) {
// cout << i << ' ' << j << ' ' << k << endl;
t = s[(i + k) % len] - s[(j + k) % len];
if (!t) k++;
else {
if (mini ^ (t > )) j += k + ;
else i += k + ;
if (i == j) j++;
k = ;
}
}
return min(i, j);
} int main() {
while (cin >> buf) {
getNext(buf);
// for (int i = 0, sz = strlen(buf); i < sz; i++) cout << next[i] + 1 << ' '; cout << endl;
int cycle = strlen(buf);
// cout << "got next" << endl;
cycle /= (cycle - next[cycle - ] - );
cout << minMaxExp(buf, true) + << ' ' << cycle << ' ' << minMaxExp(buf, false) + << ' ' << cycle << endl;
}
return ;
}
 
——written by Lyon

最新文章

  1. CI框架搭建
  2. Android 短信广播接收相关问题
  3. AC日记——字符串的展开 openjudge 1.7 35
  4. winfrom中DataGridView绑定数据控件中DataGridViewCheckBoxColumn怎么选中
  5. swift webView 提出这样的要求你能忍吗?
  6. codevs 1690 开关灯 线段树水题
  7. IPC机制
  8. Numpy中的矩阵合并
  9. 【转】shell中IFS用法
  10. .NET世界各成员之间的关系
  11. windows下使用命令查看端口占用情况
  12. Quartz的misfire处理机制分析
  13. 宏定义define和const的区别
  14. Sublime Text 3激活
  15. SQL(ORACLE)
  16. 简单易懂的程序语言入门小册子(3):基于文本替换的解释器,let表达式,布尔类型,if表达式
  17. [USACO 2018 Open Contest]作业总结
  18. 关于在win8系统下用VMware 9.0装系统导致物理机不断重启的解决办法
  19. webstorm背景颜色更改
  20. 通过经纬度获取所属城市信息-php

热门文章

  1. java中的线程(2):如何正确停止线程之2种常见停止方式
  2. JZOJ 5459 购物
  3. javascript中uber实现子类访问父类成员
  4. R语言基础画图/绘图/作图
  5. 访问Bing地图
  6. 重温 Webpack, Babel 和 React
  7. 【JZOJ4791】【NOIP2016提高A组模拟9.21】矩阵
  8. 小爬爬5:scrapy介绍2
  9. 遗传算法MATLAB实现(1):工具箱下载及安装
  10. typroa 和markdown基操