最小表示法

题意： # 给定一个循环字符串，问字典序最小的串的开始位置。 思路： # 之前用poj 1509 解题报告-字符串的最小表示法 A过

hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A

hdu 2609 题目链接 题意：给出n个循环字符串，问有多少种。 思路：将每个字符串换成最小表示，然后set存一下即可。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月13日 星期六 02时44分21秒 4File Name :code/hdu/2609.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n; 35char s[N][105]; 36set<string>se; 37int minRep(char *s) 38{ 39 int n = strlen(s); 40 int i = 0 ; 41 int j = 1 ; 42 int k = 0 ; 43 while (i<n&&j<n&&k<n) 44 { 45 int t = s[(i+k)%n] - s[(j+k)%n]; 46 if (t==0) k++; 47 else 48 { 49 if (t>0) 50 i+=k+1; 51 else j+=k+1; 52 if (i==j) j++; 53 k = 0 ; 54 } 55 } 56 return i<j?i:j; 57} 58int main() 59{ 60 #ifndef ONLINE_JUDGE 61 freopen("code/in.txt","r",stdin); 62 #endif 63 while (~scanf("%d",&n)) 64 { 65 ms(s,0); 66 se.clear(); 67 // cout<<"n:"<<n<<endl; 68 char tmp[105]; 69 for ( int i = 0 ; i < n; i++) 70 { 71 scanf("%s",tmp); 72// cout<<"tmp:"<<tmp<<endl; 73 int k = minRep(tmp); 74// cout<<"k:"<<k<<endl; 75 int cnt = 1; 76 int len = strlen(tmp); 77 for ( int j = k ; cnt <= len ; j++,cnt++) 78 s[i][cnt-1] = tmp[j%len]; 79 se.insert(string(s[i])); 80 } 81// for ( int i = 0 ; i < n; i++) cout<<"s[i]:"<<s[i]<<endl; 82// 83 int ans = se.size(); 84 printf("%d\n",ans); 85 } 86 #ifndef ONLINE_JUDGE 87 fclose(stdin); 88 #endif 89 return 0; 90}

hdu 4162 题意：给出一串代表8个方向的数字，求这串序列的一阶差分（the first difference）的字典序最小的表示。 思路：先做个变换，按照题意，第i位的一阶差分 s[i] = ((s[i+1]-s[i])+8)%8; 然后求出最小表示开始的位置。。输出即可。

poj 1509 题目链接 题意&思路：同uva 1314 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%s",s); 67 printf("%d\n",minRep(s)+1); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}

uva 1314 题目链接 题意：给定一个循环字符串，问字典序最小的串的开始位置。最小表示法裸题。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%d\n%s",&n,s); 67 printf("%d\n",minRep(s)); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}

首先放一波资料： 参考博客 对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。 一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。