题意:一个数字,依次将第一位放到最后一位,问小于本身的数的个数及等于本身的个数和大于本身的个数,但是要注意重复的不再计算。
如果按照题意直接模拟,时间复杂度会达到 Θ(|N|2) ,然而我们会发现其中有许多不必要的重复比较,这时候扩展kmp算法就派上了用场。
我们可以先把整个串复制一遍添到原串的结尾,如12121就是1212112121,做一遍扩展kmp后可求出next数组,也就是知道了 S0..nexti=Si+nexti−1 。
那么在比较的时候,前 nexti 位是相同的,只需比较下一位即可知道原串和新串的大小关系。另外要注意相等的情况,当 nexti≥|原串| 时,显然原数=新数,此时可以直接退出比较,因为已经出现了循环,后面的答案已经对最终答案没有影响。
本题的耗时主要花在做扩展kmp和比较上,因此忽略常数之后时间复杂度大约是 Θ(|N|) 。
参考程序实现:
#include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int maxlen = 1e5 + 9; int main() { int caset; scanf("%d", &caset); for(int casei = 1; casei <= caset; casei++) { char st[maxlen << 1]; scanf("%s", st); int len = strlen(st); for(int i = 0; i < len; i++) st[i + len] = st[i]; //把整个串复制一遍添到末尾 st[len + len] = '\0'; len = strlen(st); //====================扩展kmp==================== int nxt[maxlen << 1]; memset(nxt, 0, sizeof nxt); nxt[0] = len; nxt[1] = 0; for(int i = 0; st[i] == st[i + 1]; i++) ++nxt[1]; int p = 1; for(int i = 2; i < len; i++) { int u = p + nxt[p]; if(i + nxt[i - p] < u) nxt[i] = nxt[i - p]; else { int j; for(j = max(u - i, 0); st[i + j] == st[j]; j++); nxt[i] = j; p = i; } } //=============================================== int greater = 0; int equal = 1; int less = 0; for(int i = 1; i < (len >> 1) + 1; i++) { if(nxt[i] >= (len >> 1)) break; //出现相同,则后面也会相同,不必再计算 less += st[nxt[i]] > st[i + nxt[i]]; //小于原数 greater += st[nxt[i]] < st[i + nxt[i]]; //大于原数 } printf("Case %d: %d %d %d\n", casei, less, equal, greater); } return 0; }