题目大意:给出一个,字符串,每次将最前一个字符放到最后,知道形成一周,然后按照每个字符串出现的先后排个名次,现在要求求出字典序最小的字符串和字典序最大的字符串为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 3374 String Problem(KMP + 最小串),布布扣,bubuko.com
hdu 3374 String Problem(KMP + 最小串)
原文:http://blog.csdn.net/keshuai19940722/article/details/21561689