题目链接:hdu 3374 String Problem
题目大意:给出一个,字符串,每次将最前一个字符放到最后,知道形成一周,然后按照每个字符串出现的先后排个名次,现在要求求出字典序最小的字符串和字典序最大的字符串为RANK几。并输出它们的出现次数,如果出现次数不只一次,那么输出RANK值较小的。
解题思路:KMP中的求最小串,然后用最小串去原字符串中求匹配数量。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
int n, jump[N];
char s[N*2], Min[N], Max[N], t[N];
inline bool cmp (char a, char b, int id) {
if (id)
return a < b;
else
return a > b;
}
int getString (int id) {
int i = 0, j = 1, k = 0;
while (i + k < n && j + k < n) {
if (s[i+k] == s[j+k]) {
k++;
} else {
if (cmp (s[i+k], s[j+k], id))
i = i + k + 1;
else
j = j + k + 1;
k = 0;
if (i == j) j++;
}
}
return min (i, j);
}
void getJump (char* f) {
int p = 0;
for (int i = 2; i <= n/2; i++) {
while (p > 0 && f[p+1] != f[i])
p = jump[p];
if (f[p+1] == f[i])
p++;
jump[i] = p;
}
}
int KMP (char* f) {
int p = 0, ans = 0;
for (int i = 1; i <= n; i++) {
while (p > 0 && f[p+1] != s[i])
p = jump[p];
if (f[p+1] == s[i])
p++;
if (p == n/2) {
ans++;
p = jump[p];
}
}
return ans;
}
int main () {
while (scanf("%s", t) == 1) {
strcpy (s, t);
strcat (s, t);
n = strlen(s);
int l = getString(0);
int r = getString(1);
strncpy (Min+1, s+l, n/2);
strncpy (Max+1, s+r, n/2);
getJump (Min);
int cl = KMP (Min);
getJump (Max);
int cr = KMP (Max);
printf("%d %d %d %d\n", l+1, cl, r+1, cr);
}
return 0;
}
分享到:
相关推荐
HDU 1022 Train Problem I 附详细思路
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
Problem Description The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规