Chinaunix首页 | 论坛 | 博客
  • 博客访问: 332986
  • 博文数量: 78
  • 博客积分: 2536
  • 博客等级: 少校
  • 技术积分: 600
  • 用 户 组: 普通用户
  • 注册时间: 2008-04-29 01:50
文章分类

全部博文(78)

文章存档

2011年(1)

2010年(17)

2009年(52)

2008年(8)

我的朋友

分类: C/C++

2009-10-24 19:00:39

 
4月15日

循环字符串的最小表示

循环同构问题:给出两个串:s1 = “babba”s2 = “bbaba”,其中两者均看成环状的,即首尾是相接的,问:从s1的哪里断开可以得到和s2一样的串或者两者用不会相同?本题就是从s1的第2个字符’a’后面断开,可以得到与s2一样的串。这个问题就是同构问题。下面一步一步分析:

1.朴素算法(O(nm)):即尝试s1n个断开点,与s2进行比较,如果相同则找到同构位置,否则找不到。该算法仅适用于n, m规模较小情况,对于n, m 都在10000规模的长度,明显速度太慢。

2.转换为模式匹配:对于此类问题,已经有一个很好的转换思路了,即:首先构造新的模型:S=s1+s1为主串,s2为模式串。如果s1s2是循环同构的,那么s2就一定可以在S中找到匹配。否则找不到匹配则两则不能同构。而在S中寻找s2的匹配是有很多O(N+M)级的算法了,KMP算法就是这样一个优秀的算法,所以本问题转换为模式匹配后应用KMP算法,可以在O(n+m)的时间内获得问题的解

3.下面再来看看“最小表示法”在此类问题中的应用(算法思路来源于国家队的一位队员),它也可以在O(n+n)时间内求解,更大的优势还有无需KMP算法的Next数组,仅需要两个指针即可。

一.从小问题谈起

问题:有两列数a1,a2…anb1,b2…bn ,不记顺序,判断它们是否相同。eg{an} = {2, 3, 5, 7}{bn} = {2, 7, 5 3}。一眼可见两者是相同的,但是对于计算机来说,如果采用枚举算法,那么比较次数将是:n*(n-1)*(n-2)….*2*1 = n! 量级。阶乘增长之快,时间上是无法忍受的。抓住问题的本质:如果两列数相同,那么它们排序之后从头到尾肯定一样!则问题在O(nlogn)时间解决。可见这个问题的本质就在于排序(非降序)之后的序列是原序列的“最小表示”,如果两个序列的“最小表示”相同则两者就相同,否则就不相同。

启示:当两个对象有多种形式且需判断它们在某种变换规则下是否相同时,可转换为比较可以通过变换规则得到的所有表示的“最小表示”是否相同。例如本问题是不计顺序的规则,最小表示就是非降序排列后的序列。当然对于其它问题就不能简单的排序了,需要满足“在变换规则下可以达到的表示形式”。

二.最小表示法

1.首先定义一个变换规则f,判断两个事物st是否互为f本质相同,方法就是:将st转换为规则f下的最小表示形式,再比较是否相同。

2.返回到本节一开始提到的字符串循环同构问题,规则f就是“循环移动”,最直接最简单的方法就是分别求出s1, s2的最小表示,再比较两者是否相同,但是可以发现这明显也是一个O(n^2)思路。

3.换一种思路,令Min(s)返回值为:从s的第Min(s)个字符引起的s的一个循环表示的最小表示,若有多个值则返回下标最小的一个。例如s = {bbbaab},那么Min(s) = 3 --下标从0算起。Min(s)的求法在后面部分具体阐述,这个问题仅仅用到这个概念,不必直接求,因为当找到循环同构时实际就是Min(s)

4.先类似于模式匹配方法将两者加倍:u = s1 + s1w = s2 + s2,指针ij分别指向u, w的第一个位置0ij指针滑动可以得到两种情况:

(1) ij分别指向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 = 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)

(2)   同样的分析,如果u[i+k] > w[j+k]:那么j可以滑动到j+k+1可保证j<=Min(s2)

综上,也就是说,两指针向后滑动比较失败以后,指向较大字符的指针向后滑动k+1个位置,直到出现如下情况

(1)   最后两指针指向的位置,向后面(包括自身起始位置)比较了len个字符都匹配成功时,那两个位置i, j就分别是s1s2的“最小表示”的位置;

(2)   或者i, j两个指针其中一个移动到>= len的位置,那么表示s1s2无法循环同构。以实例分析,假设s1=‘babba’s2=‘bbaba’。那么有

      u = ‘b a b b a b a b b a’

      w = ‘b b a b a b b a b a’

按照上面分析的方法,i,j指针都指向0,然后滑动,那么在i = 4, j = 2时会出现连续5个字符相等:u[48] = w[26],所以s1s2是循环同构的,同构位置在s1i = 4s2j = 2处。实际也都是它们最小表示的位置。

至此,循环同构的这个O(n)级的算法介绍完毕,不得不说提出这个算法思想的人属于天才级别的,很类似于KMP的思路,但是却仅适用两个指针实现了O(n)的算法。下面将分别就这个算法,展开两个问题的具体求解。

1.求字符串的循环最小表示

上面说的两个字符串同构的,并没有直接先求出Min(s),而是通过指针移动,当某次匹配串长时,那个位置就是Min(s)。而这里的问题就是:不是给定两个串,而是给出一个串,求它的Min(s)egMin(“babba”) = 4。那么由于这里并非要求两个串的同构,而是直接求它的最小表示,由于源串和目标串相同,所以处理起来既容易又需要有一些变化:我们仍然设置两个指针,p1, p2,其中p1指向s[0]p2指向s[1],仍然采用上面的滑动方式:

(1)  利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。

(2)  k = 0开始,检验s[p1+k] s[p2+k] 对应的字符是否相等,如果相等k++,一直下去,直到找到第一个不同,(k试了一个字符串的长度也没找到不同,则那个位置就是最小表示位置,算法终止并返回)。则该过程中,s[p1+k] s[p2+k]的大小关系,有三种情况:

     (A). s[p1+k] > s[p2+k],则p1滑动到p1+k+1 --- s1[p1->p1+k]不会

      是该循环字符串的“最小表示”的前缀。

     (B). s[p1+k] > s[p2+k],则p1滑动到p1+k+1处,原因同上。

     (C). s[p1+k] = s[p2+k],则 k++ if (k == len) 返回结果。

    注:这里滑动方式有个小细节,若滑动后p1 == p2,将正在变化的那个指针再+1。直到p1p2把整个字符串都检验完毕,返回两者中小于 len 的值。

(3)   如果 k == len 则返回p1p2中的最小值

      如果 p1 >= len   则返回p2

      如果 p2 >= len   则返回p1

(4)   进一步的优化,例如:p1要移到p1+k+1时,如果p1+k+1 <= p2的话,可以直接把p1移到 p2之前,因为,p2p2+k已经检验过了该前缀比以p1p1+k之间任何一个位前缀都小;p2时的类似,移动到p1+1

至此,求一个字符串的循环最小表示在O(n)时间实现,感谢大牛的论文。其中实现时的小细节“如果滑动后p1 == p2,将正在变化的那个指针再+1,开始没有考虑,害得我想了几个小时都觉得无法进行正确的移动。具体例题有两个: 20061729题。一个是10000规模一个是100000规模。运行时间前者是0S,后者是0.05S。代码见后一贴。

 

循环字符串的最小表示2

2.判断两个字符串是否同构

算法已经描述了,这里再简写一下:

(1)   将两者均加倍:u = s1+s1, w = s2+s2i指向u[0]j指向w[0];

(2)   k = 0 开始,比较u[i+k] v[j+k],如果相等则k++,如果k == len那么存储匹配的两个位置并返回true。否则:

u[i+k] > v[j+k],则i向前滑动到i+k+1break

u[i+k] < v[j+k],则j向前滑动到j+k+1break

(2)   如果i, j其中一个已经大于等于长度len(没有加倍前的长度),那么两者肯定不是循环同构,直接返回两个false

可见,基本跟前面循环最小表示算法实现差不多,唯一区别是不能直接进行那个优化,因为这里的源串和目标串并不一样,而且也不用某次当p1 == p2时,将正在变化的指针+1。这就是两个不同问题唯一不同的地方了。
 
附1:-- 返回字符串循环最小表示的位置
 
int MinCircularDenote(const char* s, int len) {
    int p1 = 0, p2 = 1, k, t1, t2;
   
    while (1) {
        k = 0;
        while (1) {
            t1 = (p1+k)%len; t2 = (p2+k)%len;
            if(s[t1] > s[t2]) {
                if (p1+k+1 <= p2) p1 = p2+1;             // optimize 
                else p1 = p1+k+1;
               
                if (p1 >= len) return p2;                     // p1 has checked len, return p2
                break;
            }   
            else if (s[t1] < s[t2]) {
                if (p2+k+1 <= p1) p2 = p1+1;
                else p2 = p2+k+1;
               
                if (p2 >= len) return p1; 
                break;
            }    
            else k++;
            if (k == len)                                         // has macthed len,return Min pos 
                return (p1        }    
    }    
}
 
附2:-- 返回两个字符串是否同构(调用前记得加倍)
 
bool CircularMatch(const char* s1, const char* s2, int len, int& pos1, int& pos2) {
    int p1 = 0, p2 = 0, k, t1, t2;
    pos1 = pos2 = -1;
   
    while (1) {
        k = 0;
        while (1) {
            t1 = (p1+k)%len; t2 = (p2+k)%len;
            if(s1[t1] > s2[t2]) {
                p1 = p1+k+1;               
                if (p1 >= len) return false; 
                break;
            }   
            else if (s1[t1] < s2[t2]) {
                p2 = p2+k+1;               
                if (p2 >= len) return false;  
                break;
            }    
            else k++;
            if (k == len) {                                      // ok, find answer  
                pos1 = p1; pos2 = p2;
                return true;
            }   
        }    
    }    
}
阅读(1717) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~