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