Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2057 Accepted Submission(s): 897
1 1 6 1
1 6 1 6
1 3 2 3
/** 题意:给一个串,然后求串的最小表示法和最大表示法,并且输出有几个 做法:串的最小表示法 + KMP **/ #include <iostream> #include <algorithm> #include <cmath> #include <string.h> #include <stdio.h> #include <queue> #include <map> #define maxn 1000005 using namespace std; int mmin, mmax; int len; char t1[maxn]; char str[maxn << 1]; char t2[maxn]; void kmp_pre(char x[], int m, int nxt[]) { int i, j; j = nxt[0] = -1; i = 0; while(i < m) { while(-1 != j && x[i] != x[j]) { j = nxt[j]; } nxt[++i] = ++ j; } } int nxt[maxn]; int kmp_count(char x[], int m, char y[], int n) { int i, j; int ans = 0 ; kmp_pre(x, m, nxt); i = j = 0; while(i < n) { while(-1 != j && y[i] != x[j]) { j = nxt[j]; } i++; j++; while(j >= m) { ans ++; j = nxt[j]; } } return ans; } void matchmin(char s[]) { int i, j, k, l; int N = len; for(i = 0, j = 1; j < N;) { for(k = 0; k < N && s[i + k] == s[j + k]; k++); if(k >= N) { break; } if(s[i + k] < s[j + k]) { j += k + 1; } else { l = i + k; i = j; j = max(l, j) + 1; } } mmin = i + 1; } void matchmax(char s[]) { int i, j, k, l; int N = len; for(i = 0, j = 1; j < N;) { for(k = 0; k < N && s[i + k] == s[j + k]; k++); if(k >= N) { break; } if(s[i + k] > s[j + k]) { j += k + 1; } else { l = i + k; i = j; j = max(l, j) + 1; } } mmax = i + 1; } int main() { while(~scanf("%s", str)) { int n; string tmp; len = strlen(str); for(int i = 0; i < len; i++) { str[i + len] = str[i]; } matchmin(str); matchmax(str); for(int i = 0; i < len; i++) { t1[i] = str[i + mmin - 1]; t2[i] = str[i + mmax - 1]; } int res1 = kmp_count(t1, len, str, len + len); int res2 = kmp_count(t2, len, str, len + len); if(mmin == 1) { res1 --; } if(mmax == 1) { res2 --; } printf("%d %d %d %d\n", mmin, res1, mmax, res2); } return 0; }
原文:http://www.cnblogs.com/chenyang920/p/4852586.html