最小表示法在解决判断“同构”一类问题中有很大作用。 循环同构问题：给出两个串：s1 = “babba”和s2 = “bbaba”，其中两者均看成环状的，即首尾是相接的，问：从s1的哪里断开可以得到和s2一样的串或者两者不会相同？本题就是从s1的第2个字符’a’后面断开，可以得到与s2一样的串。这个问题就是同构问题。
1.朴素算法(O(nm))：即尝试s1的n个断开点，与s2进行比较，如果相同则到同构位置，否则不到。该算法仅适用于n, m规模较小情况，对于n, m 都在10000规模的长度，明显速度太慢。 2.转换为模式匹配：对于此类问题，已经有一个很好的转换思路了，即：首先构造新的模型：S=s1+s1为主串，s2为模式串。如果s1和s2是循环同构的，那么s2就一定可以在S中到匹配。否则不到匹配则两则不能同构。而在S中寻s2的匹配是有很多O(N+M)级的算法了，KMP算法就是这样一个优秀的算法，所以本问题转换为模式匹配后应用KMP算法，可以在O(n+m)的时间内获得问题的解。
3.下面再来看看“最小表示法”在此类问题中的应用（算法思路来源于国家队的一位队员），它也可以在O(n+n)时间内求解，更大的优势还有无需KMP算法的Next数组，仅需要两个指针即可。
解析过程：
问题：有两列数a1,a2…an和b1,b2…bn ，不记顺序，判断它们是否相同。eg：{an} = {2, 3, 5, 7}；{bn} = {2, 7, 5 3}。一眼可见两者是相同的，但是对于计算机来说，如果采用枚举算法，那么比较次数将是：n*(n-1)*(n-2)….*2*1 = n! 量级。阶乘增长之快，时间上是无法忍受的。抓住问题的本质：如果两列数相同，那么它们排序之后从头到尾肯定一样！则问题在O(nlogn)时间解决。可见这个问题的本质就在于排序（非降序）之后的序列是原序列的“最小表示”，如果两个序列的“最小表示”相同则两者就相同，否则就不相同。
书录解题
启示：当两个对象有多种形式且需判断它们在某种变换规则下是否相同时，可转换为比较可以通过变换规则得到的所有表示的“最小表示”是否相同。例如本问题是不计顺序的规则，最小表示就是非降序排列后的序列。当然对于其它问题就不能简单的排序了，需要满足“在变换规则下可以达到的表示形式”。 a.首先定义一个变换规则f，判断两个事物s和t是否互为f本质相同，方法就是：将s，t转换为规则f下的最小表示形式，再比较是否相同。
b.返回到本节一开始提到的字符串循环同构问题，规则f就是“循环移动”，最直接最简单的方法就是分别求出s1, s2的最小表示，再比较两者是否相同，但是可以发现这明显也是一个O(n^2)思路。 中华会务网
c.换一种思路，令Min(s)返回值为：从s的第Min(s)个字符引起的s的一个循环表示的最小表示，若有多个值则返回下标最小的一个。例如s = {bbbaab}，那么Min(s) = 3 --下标从0算起。Min(s)的求法在后面部分具体阐述，这个问题仅仅用到这个概念，不必直接求，因为当到循环同构时实际就是Min(s)。
d.先类似于模式匹配方法将两者加倍：u = s1 + s1，w = s2 + s2，指针i，j分别指向u, w的第一个位置0，i，j指针滑动可以得到两种情况：
<1>.若i，j分别指向Min(s1)和Min(s2)时，一定有u[i…i+|s1|-1] = w[j…j+|s2|+1]也就是立马得到解。木结构设计规范
<2>.否则i<=Min(s1)，j<=Min(s2)时，两指针仍然有希望到达i=Min(s1)，j=Min(s2)这个状态。
因此问题转换为：两个指针分别向后滑动比较，如果比较失败，如何正确的滑动指针使得新指针i, j仍然满足：i<=Min(s1)，j<=Min(s2)。设指针i,j分别向后滑动k个位置后比较失败(k>=0)，即有u[i+k]≠w[j+k]。仍然分两种情况：
<1>. u[i+k] > w[j+k]：令i<=x<=i+k时，我们来研究s1[x-1]，因为u[x]在u[i]的后x-i个位置，对应相等于在w[j]的后x-i个位置即w[j+(x-i)]，同样对应相等的u[x+1] = w[j+(x+1-i)]…直到x =i+ k-1，即有：u[x…x+i+k-1] = w[j+x-i…j+x-1]，现在已经在u[i+k]位置处不相等且u[i+k]>w[j+k]，因此整个s[x-1]都不是s1的最小表示的前缀，则Min(s1)>i+k，所以i可以滑动到i+k+1仍可保证<=Min(s1)。
/*
tju 3275(Windy's S), zju2006(Glass Beads),zju1729(Hidden Password), hdu3374(String Problem
)
*/
#include <iostream>
#include <string>
using namespace std;
/*
用最小表示法求字符串S的最小字典序
返回字典序最小的串的首字母位置
*/
int MinRepresstation(string S)
{
int i = 0, j = 1, k = 0;
int len = S.length();
S += S;
while(i < len && j < len)
{
k = 0;
2011山东理综
路亚中国 while(k < len && S[i + k] == S[j + k])
k++;
if(k >= len)
break;
if(S[i + k] > S[j + k])
i = max(i + k + 1, j + 1);
else
j = max(i + 1, j + k + 1);
seer2.61 }
return min(i ,j);
}
int main()
{
int T;
string S;
int beg, k, len;
cin>>T;
while(T--)
{
cin>>len>>S;
beg = MinRepresstation(S);
cout<<beg<<endl;
}
return 0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议