关于字符串的交迭与边界问题算法的一些回顾

       又见字符串算法，看到那个交迭和边界的算法，真是看到脑壳痛。由于原文资料还是英文的，上周就在那翻译了，还没仔细看过，也不知道翻译的对不对，今晚拿着打印版的跑到教室坐了会，假日人少但很清静！整个晚上光看交迭和边界问题了。文章算法给出来了，不至于看不懂吧，但实际上就是看不懂。经过一步步的画啊，终于有了些眉目。抓紧机会好好整理再回顾下：

  

    ①：什么叫两个字符串x和y的交迭？很简单，就是尽可能多的获取x的结尾部分和y的开头部分之间的交集。如：abacaba和acabaca 的交换长度就是5   因为有abacaba  acabaca。  字符串x和字y的交迭表示为 overlap(x,y)。

    

  ②：什么叫字符串x的边界?字符串x的边界就是x和x的交迭。如：abaababa的边界就是3，因为有 abaababa  abaababa  字符串x的边界记为border(x)，显然有border(x)=overlap(x,x)。

      正因为有②中overlap(x,x)=border(x)的关系，所以这两个问题其实可以归并到一个问题中来，这里都归到边界算法中来，为什么，按我弱弱的想法，后者少一个参数。嘿嘿。

    

  扩展：当x是y的前缀，a是字母时，有overlap(xa,y)=border(xa)。例如：x=aba, y=x#=aba#，xa=abaa那么有overlap(xa,y)=overlap(abaa,aba#)=1,因为abaa aba#,同时border(xa)=overlap(xa,xa)=overlap(abaa,abaa)=1  因为abaa abaa。

   

  我们假定z=overlap(x,y)。那么有公式一：

overlap(xa,y)=① za   za是y的前缀

                       ② border(za)    其他 

    又设u=border(z)，对每个字母a，有公式二：

border(za)=① ua    ua是x的前缀

                   ②border(ua)  其他

 

   公式一的②情况又可以用公式二来解决，于是交迭问题归并到边界问题中来解决。

 

   现在用下面这一算法来解决边界问题：

计算长度为m的一个字符串x的边界的长度，设定一个包含m+1个整数的数组b,使得b[j]是字符串x[0,1...j-1]的边界的长度。特别的，border(x)的长度就是b[m]，这里规定b[0]=-1。

 

 Border算法的实现：

//Border算法
public class Border {
     public void Border(String x) {
          int m = x.length; 
          int b[0] = -1;   
          for(j = 1;j <= m-1;j++) {
                b[j] = i;    
                while(i >= 0 && x[j]!=x[i]) {
                       i = b[i];  //先比较x[1]和x[0],若不相等继续x[2]比较x[0],直到x[i]=x[0],接下来就比x[i+1]和x[1]，如此一直比下去..   
                }
                i++;
          }
         b[m]=i;
         System.out.println( b[m]);
     }
}

 

上面就是算法的精华。我好像看到过一片文章大概意思差不多，但好懂些,不早了，睡觉了，明天找找。GoodNight!