---

最小表示法

這是一個簡單的字符串算法，其解決的問題如下：

給定一個字符串\(S\)，長度為\(n\)，如果把它的最后一個字符不斷放到最前面，會得到\(n\)個不同的字符串，那么我們稱這\(n\)個字符串是循環同構的。這\(n\)個字符串中字典序最小的一個，我們就稱為\(S\)的最小表示。

\(For\ example:\)

\(S=abcda,S_1=aabcd,S_2=daabc,S_3=cdaab,S_4=bcdaa\)

其中，\(S\)的最小表示為\(S_1\)。

了解了概念以后，我們將介紹一種算法，可以在\(O(n)\)的時間內求出一個字符串的最小表示。

對于一個環，最樸素的方法就是復制一倍接在原序列后面，這里我們就要用到這種方法:令字符串\[S'_i=\begin{cases}1 \leq i\leq n ,S_i\\n<i \leq 2n ,S_{i-n}\end{cases}\]

然后，利用兩個指針\(i,j\)掃描字符串\(S'\)，其具體方法如下：

1.初始化\(i=1,j=2\)
2.直接向后掃描，比較兩個循環同構串\(S'(i,i+n-1),S'(j,j+n-1)\)
2.(1) 如果掃描了\(n\)個字符兩個串仍然相等，則說明這個字符串只由一個字符構成，任意位置開頭都是最小表示
2.(2) 找到位置\(S'_{i+k} != S'_{j+k}\)，若\(S'_{i+k} > S'_{j+k}\)，則說明位置\(j\)更優，更新位置\(i=i+k+1\)，若\(S'_{i+k} < S'_{j+k}\)，則說明位置\(i\)更優，更新位置\(j=j+k+1\)
3.若\(i>n\)，則說明位置\(j\)為最小表示，若\(j>n\)，則說明位置\(i\)為最小表示

為什么\(S'_{i+k} > S'_{j+k}\)時，直接將\(i\)更新為\(i+k+1\)呢，相信這是最大的一個疑問。

\(Explain:\)

當\(S'_{i+k} > S'_{j+k}\)時，顯然\(S'_i\)不是最小表示，因為存在一個更優的最小表示\(S'_j\)。然而，\(S'_{i+p}(1 \leq p \leq k)\)均不是最小表示，對于任意的一個\(S'_{i+p}\)，一定也存在一個\(S'_{j+p}\)比它更優，因為它們不斷向后比較，同樣會在\(i+k\)處發現有\(S'_{i+k} > S'_{j+k}\)。這樣就說明了當一個\(i\)在\(i+k\)的位置發現不優時，\(i+k\)以前的也均不優，直接將\(i\)更新為\(i+k+1\)即可。

同理，發現\(j\)不優時也是一樣的。

\(Code:\)

inline void solve(void) {int ans;int i=1,j=2,k;while(i<=n&&j<=n){for(k=0;k<=n&&s[i+k]==s[j+k];k++);if(k==n)break;if(a[i+k]>a[j+k]){i=i+k+1;if(i==j)i++;}else{j=j+k+1;if(i==j)j++;}}ans=min(i,j); }

Necklace

Description

有一天，袁同學綿了一條價值連城寶石項鏈，但是，一個嚴重的問題是，他竟然忘記了項鏈的主人是誰！在得知此事后，很多人向袁同學發來了很多郵件，都說項鏈是自己的，要求他歸還（顯然其中最多只有一個人說了真話）。袁同學要求每個人都寫了一段關于自己項鏈的描述： 項鏈上的寶石用數字0至9來標示。一個對于項鏈的表示就是從項鏈的某個寶石開始，順指針繞一圈，沿途記下經過的寶石，比如如下項鏈： 1-2-3-4 　　

它的可能的四種表示是0123、1230、2301、3012。

袁☆同學現在心急如焚，于是他找到了你，希望你能夠編一個程序，判斷兩個給定的描述是否代表同一個項鏈（注意，項鏈是不會翻轉的）。

給定兩個項鏈的表示，判斷他們是否可能是一條項鏈。

Input Format

輸入文件只有兩行，每行一個由0至9組成的字符串，描述一個項鏈的表示（保證項鏈的長度是相等的）。

Output Format

如果兩條項鏈不可能同構，那么輸出’No’，否則的話，第一行輸出一個’Yes’

第二行輸出該項鏈的字典序最小的表示。 設L = 項鏈長度，L <= 1000000。

Sample Input

2234342423 2423223434

Sample Output

Yes 2234342423

解析

這就是一道最小表示法模板題，直接將兩個串分別轉為最小表示法，再比較是否相同即可。如果相同，直接將最小表示法輸出。

\(Code:\)

#include<bits/stdc++.h> using namespace std; const int N=1000000+20; int lena,lenb; char a[N*2],b[N*2],Mina[N],Minb[N]; inline void input(void) {scanf("%s",a+1);scanf("%s",b+1);lena=strlen(a+1);lenb=strlen(b+1);for(int i=1;i<=lena;i++)a[lena+i]=a[i];for(int i=1;i<=lenb;i++)b[lenb+i]=b[i]; } inline void solvea(void) {int ans;int i=1,j=2,k;while(i<=lena&&j<=lena){for(k=0;k<=lena&&a[i+k]==a[j+k];k++);if(k==lena)break;if(a[i+k]>a[j+k]){i=i+k+1;if(i==j)i++;}else{j=j+k+1;if(i==j)j++;}}ans=min(i,j);for(int p=1;p<=lena;p++)Mina[p]=a[ans+p-1]; } inline void solveb(void) {int ans;int i=1,j=2,k;while(i<=lenb&&j<=lenb){for(k=0;k<=lenb&&b[i+k]==b[j+k];k++);if(k==lenb)break;if(b[i+k]>b[j+k]){i=i+k+1;if(i==j)i++;}else{j=j+k+1;if(i==j)j++;}}ans=min(i,j);for(int p=1;p<=lenb;p++)Minb[p]=b[ans+p-1]; } int main() {input();solvea();solveb();int flag=1;if(lena!=lenb){printf("No\n");return 0;}for(int i=1;i<=lena;i++)if(Mina[i]^Minb[i])flag=0;if(!flag){printf("No\n");return 0;}else{printf("Yes\n");for(int i=1;i<=lena;i++)printf("%c",Mina[i]);puts("");}return 0; }

---

轉載于:https://www.cnblogs.com/Parsnip/p/10574375.html

總結

以上是生活随笔為你收集整理的『最小表示法 Necklace』的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。