【概述】

最大最小表示法用于解決字符串的同構(gòu)問(wèn)題，其在復(fù)雜度為 O(n) 的時(shí)間內(nèi)求出一個(gè)字符串的所有同構(gòu)串中字典序最大（小）的串的起始位置。

應(yīng)用：

• 給出 n 個(gè)循環(huán)字符串判斷有多少不同字符串：逐個(gè)用最大（小）表示法表示，然后加入 set 去重
• 循環(huán)字符串所有同構(gòu)串中字典序最大（小）的表示：用最大（小）表示法求出起始位置，輸出即可
• 判斷兩個(gè)字符串是否同構(gòu)：將兩字符串用最大（小）表示法表示，然后逐個(gè)字符比較

【算法原理】

設(shè)一字符串 S，且 S’ 是 S 的循環(huán)同構(gòu)的串的最小表示，那么對(duì)于字符串循環(huán)同構(gòu)的最小表示法，其問(wèn)題實(shí)質(zhì)是求 S 串的一個(gè)位置，從這個(gè)位置開(kāi)始循環(huán)輸出 S，得到的 S’ 字典序最小。

最樸素的算法是設(shè) i、j 兩個(gè)指針，i 指向最小表示的位置，j 作為比較指針。

令 i=0，j=1，那么：

• 若 S[i]>S[j]，則：i=j，j=i+1
• 若 S[i]<S[j]，則：j++
• 若?S[i]=S[j]，則設(shè)指針 k，分別從 i 和 j 位置向下比較，直到 S[i]!=S[j]
  若 S[i+k]>S[j+k]，則：i=j，j=i+1
  否則?j++

最后返回 i 即可

可以看出，樸素算法在 S[i]=S[j] 時(shí)，i 的指針移動(dòng)的太少了，在遇到像 bbb…bbbbbba 這樣復(fù)雜的字符串時(shí)，時(shí)間復(fù)雜度可能會(huì)退化到 O(n^2)，針對(duì)這一問(wèn)題加以改進(jìn)可得到 O(n) 的最小表示法的算法，其核心思路是在 S[i]=S[j] 時(shí)同時(shí)維護(hù) i、j 兩個(gè)指針

同樣令 i=0，j=1，那么：

• 若 S[i]>S[j]，則：i=j，j=i+1
• 若 S[i]<S[j]，則：j++
• 若?S[i]=S[j]，則設(shè)指針 k，分別從 i 和 j 位置向下比較，直到 S[i]!=S[j]
  若 S[i+k]>S[j+k]，則：i=i+k
  否則?j++

最后返回 i 和 j 的小者即可

【實(shí)現(xiàn)】

1.最小表示法

int minmumRepresentation(char *str){//最小表示法int len=strlen(str);int i=0;//指向字符串最小的位置int j=1;//比較指針int k=0;//str[i]與str[j]相等時(shí)一次移動(dòng)幾個(gè)while(i<len&&j<len&&k<len){int temp=str[(i+k)%len]-str[(j+k)%len];//比較值的長(zhǎng)度if(temp==0)k++;else{if(temp>0)//維護(hù)ii=i+k+1;else//維護(hù)jj=j+k+1;if(i==j)//相等時(shí)比較指針后移j++;k=0;}}return i<j?i:j;//返回i、j中較小的那個(gè) }

2.最大表示法

int maxmumRepresentation(char *str){//最大表示法int len=strlen(str);int i=0;//指向字符串最小的位置int j=1;//比較指針int k=0;//str[i]與str[j]相等時(shí)一次移動(dòng)幾個(gè)while(i<len&&j<len&&k<len){int temp=str[(i+k)%len]-str[(j+k)%len];//比較值的長(zhǎng)度if(temp==0)k++;else{if(temp>0)//維護(hù)ij=j+k+1;else//維護(hù)ji=i+k+1;if(i==j)//相等時(shí)比較指針后移j++;k=0;}}return i<j?i:j;//返回兩者最小值 }

【例題】

How many（HDU-2609）(最小表示法求不同構(gòu)串個(gè)數(shù))：點(diǎn)擊這里

String Problem（HDU-3374）(最小最大表示法+kmp)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的字符串处理 —— 最大最小表示法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。