模板
int getMin(char *s) { int i = 0, j = 1, l; int len = strlen(s); while(i < len && j < len) { for(l = 0; l < len; l++) if(s[(i + l) % len] != s[(j + l) % len]) break; if(l >= len) break; if(s[(i + l) % len] > s[(j + l) % len]) { if(i + l + 1 > j) i = i + l + 1; else i = j + 1; } else if(j + l + 1 > i) j = j + l + 1; else j = i + 1; } return i < j ? i : j; } int getMax(char *s) { int len = strlen(s); int i = 0, j = 1, k = 0; while(i < len && j < len && k < len) { int t = s[(i+k)%len]-s[(j+k)%len]; if(!t) k++; else { if(t > 0) { if(j+k+1 > i) j = j+k+1; else j = i+1; } else if(i+k+1 > j) i = i+k+1; else i = j+1; k = 0; } } return i < j ? i : j; }
问题提出 : 给出一个字符串求出字符串的最大or最小表示法
分析 : 参考==>http://blog.csdn.net/cillyb/article/details/78058174
一般来说就是能够解决字面意思的题意以及一些字符串同构问题
相关题目 :
① HDU 2609
题意 : 给出 n 个字符串，问你有多少不同的字符串，其中同构的字符串算作一种
分析 : 用最大or最小表示法将所有字符串“同化”然后装到set容器判重
#include<stdio.h> #include<string> #include<set> #include<algorithm> #include<string.h> #include<iostream>
using namespace std; int len; int getMin(string & s) { int i = 0, j = 1, l; while(i < len && j < len) { for(l = 0; l < len; l++) if(s[(i + l) % len] != s[(j + l) % len]) break; if(l >= len) break; if(s[(i + l) % len] > s[(j + l) % len]){ if(i + l + 1 > j) i = i + l + 1; else i = j + 1; } else if(j + l + 1 > i) j = j + l + 1; else j = i + 1; } return i < j ? i : j; } int main(void) { int n; string s, into; while(~scanf("%d", &n)){ set<string> cnt; for(int i=0; i<n; i++){ cin>>s; len = s.length(); int idx = getMin(s); into.clear(); for(int j=0; j<len; j++){ into.append(1, s[ (idx+j)%len ]); /// 在末尾插入一个s[(idx+j)%len]字符
} //cout<<into<<endl;
cnt.insert(into); } printf("%d\n", cnt.size()); } return 0; }
② HDU 3374
题意 : 给出一个字符串，叫你给出要构成最大or最小表示法字符串开头应该在的位置，然后就是计算一下这个表示法下字符串循环节出现次数
分析 : KMP + 最大最小模板即可解决
#include<string.h> #include<stdio.h>
using namespace std; const int maxn = 1e6 + 10; char mo[maxn], s[maxn]; int Next[maxn], moL, len; int getMax() { int i = 0, j = 1, k = 0; while(i < len && j < len && k < len) { int t = s[(i+k)%len]-s[(j+k)%len]; if(!t) k++; else { if(t > 0) { if(j+k+1 > i) j = j+k+1; else j = i+1; } else if(i+k+1 > j) i = i+k+1; else i = j+1; k = 0; } } return i < j ? i : j; } int getMin() { int i = 0, j = 1, l; while(i < len && j < len) { for(l = 0; l < len; l++) if(s[(i + l) % len] != s[(j + l) % len]) break; if(l >= len) break; if(s[(i + l) % len] > s[(j + l) % len]){ if(i + l + 1 > j) i = i + l + 1; else i = j + 1; } else if(j + l + 1 > i) j = j + l + 1; else j = i + 1; } return i < j ? i : j; } inline void GetNext() { int i = 0, j = -1; Next[i] = j; while(i < moL){ while(j!=-1 && mo[i]!=mo[j]) j = Next[j]; Next[++i] = ++j; } } inline void PrintAns() { int idx = getMin(); for(int i=0; i<moL; i++) mo[i] = s[ (idx+i)%moL ]; mo[moL] = '\0'; GetNext(); printf("%d %d ", ++idx, Next[moL]==0?1:moL/(moL-Next[moL])); idx = getMax(); for(int i=0; i<moL; i++) mo[i] = s[ (idx+i)%moL ]; mo[moL] = '\0'; GetNext(); printf("%d %d\n", ++idx, Next[moL]==0?1:moL/(moL-Next[moL])); } int main(void) { while(~scanf("%s", s)){ len = moL = strlen(s); PrintAns(); } return 0; }