隐藏密码(字符串的同构与最小表示法)
详情可参照:
{
循环字符串的最小表示法的问题可以这样描述:
对于一个字符串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++ ,