当前位置:编程学习 > C/C++ >>

隐藏密码(字符串的同构与最小表示法)

 
详情可参照:
循环字符串的最小表示法的问题可以这样描述:
对于一个字符串S,求S的循环的同构字符串S’中字典序最小的一个。
由于语言能力有限,还是用实际例子来解释比较容易:
设S=bcad,且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。
对于字符串循环同构的最小表示法,其问题实质是求S串的一个位置,从这个位置开始循环输出S,得到的S’字典序最小。
一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置,j作为比较指针。
令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S[i+k] > S[j+k] i=j,j=i+1
         否则j++
返回i
起初,我想在j指针后移的过程中加入一个优化。就是j每次不是加1,而是移动到l位置。其中,l>j且S[l]<=S[j]。但是,即使加入这一优化,在遇到bbb…bbbbbba这样的字符串时复杂度将退化到O(n^2)。
注意到,朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。
令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i]==S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S[i+k] > S[j+k] i=i+k
         否则j++
返回i和j的小者
注意到上面两个算法唯一的区别是粗体的一行。这一行就把复杂度降到O(n)了。
值得一提的是,与KMP类似,最小表示法处理的是一个字符串S的性质,而不是看论文时给人感觉的处理两个字符串。
应用最小表示法判断两个字符串同构,只要将两个串的最小表示求出来,然后从最小表示开始比较。剩下的工作就不用多说了。
 
int MinimumRepresentation(char *s, int l)  
{  
    int i = 0, j = 1, k = 0, t;  
    while(i < l && j < l && k < l) {  
        t = s[(i + k) >= l ? i + k - l : i + k] - s[(j + k) >= l ? j + k - l : j + k];  
        if(!t) k++;  
        else{  
            if(t > 0) i = i + k + 1;  
            else j = j + k + 1;  
            if(i == j) ++ j;  
            k = 0;  
        }  
    }  
    return (i < j ? i : j);  
}  

 

这段文字
那么以上就是字符串的最小表示法……(我能告诉你我一开始想的是后缀自动机TNT。。。)
具体我也在研究……(又一“科技黑箱”???)
 
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
#include<cassert>  
#include<climits>  
using namespace std;  
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define MEM(a) memset(a,0,sizeof(a))  
#define MEMI(a) memset(a,127,sizeof(a))  
#define MEMi(a) memset(a,128,sizeof(a))  
#define INF (2139062143)  
#define F (1000000009)  
#define MAXN (5000000+10)  
typedef long long ll;  
int n;  
char s[MAXN*2];  
int main()  
{  
   freopen("hidden.in","r",stdin);  
   freopen("hidden.out","w",stdout);  
   scanf("%d%/n",&n);  
   for(int i=1;i<=n;i+=72) gets(s+i);  
     
   copy(s+1,s+1+n+1,s+n+1);  
   int i=1,j=2;  
   for(int k=0;k<=n&&i<=n&&j<=n;)  
   {  
        if (s[i+k]==s[j+k]) k++;  
        else   
      {  
         if (s[i+k]>s[j+k]) i=i+k+1;  
        else j=j+k+1;  
           if(i==j) j++;  
           k=0;  
      }  
   }  
   cout<<min(i,j)-1<<endl;  
     
// while(1);  
   return 0;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,