"因祸得福" ---字符串交迭和边界问题的继续回顾

        昨天那个border算法我说好像在哪里见过，原来就是KMP算法中的精髓部分。KMP算法我以前是看过的，现在足以表明我看的是多么肤潜，或者说根本就没弄懂他的意思。以前对KMP算法的next[]函数引入是佩服的五体投地，四脚朝天，但对next[]函数并没有更深入的了解，想起昨天从字符串的边界问题引出了KMP算法，现在方知，KMP算法归根到底也是字符串的交迭和边界问题啊。岂非因祸得福！

        关于KMP算法，网上有一篇绝妙的文章，个人认为是介绍的最通俗易懂的了。作者是A_B_C_ABC，原文地址：http://blog.csdn.net/A_B_C_ABC/archive/2005/11/25/536925.aspx 。看看里面串的模式值next[n]的定义：

（1）next[0]= -1  意义：任何串的第一个字符的模式值规定为-1。

（2）next[j]= -1  意义：模式串T中下标为j的字符，如果与首字符

     相同，且j的前面的1—k个字符与开头的1—k

    个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。

     如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]

（3）next[j]=k    意义：模式串T中下标为j的字符，如果j的前面k个

     字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。

                       即T[0]T[1]T[2]。。。T[k-1]==T[j-k]T[j-k+1]T[j-k+2]…T[j-1]

且T[j] != T[k].（1≤k<j）;

(4) next[j]=0   意义：除（1）（2）（3）的其他情况。

对比border(x)的定义：

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

border的复杂就体现在它把这么多话就压成这么二句话了，当然原文作者也根本就没提到KMP算法。至此大体解决了昨天的疑惑。

 

举个例子实战一下：给定字符串 x = abaababa,打印出数组b。

//border算法的一个应用
public class Border() {
       public void Border(String x,char [] y) {
           int m = x.length();
           int [] b = new int[x.length()+1];
           int i = 0;
           b[0] = -1;

           for(int j = 1;j <= m-1; j++) {
                  b[j] = i;
                  while( i >= 0 && y[j] != y[i]) {
                         i = b[i];
                   }
                   i++;
           }
            b[m] = i;    //border算法
            for(int k = 0;k < m+1; k++) {
                    System.out.println(b[k] + "  ");
            }
       }

        public static void main(String[] args) {
              Border border = new Border();
              char []X = {'a','b','a','a','b','a','b','a'};
              String str = new String(X);
              border.Border(str,X);   
        }
}

 

 在C++中可以只用到String s = "abaababa"，不知道这里可以一步到位吗？

 分析结果，其实可以看出来 border(x)=3,因为有 abaababa  abaababa。

当m = 0时 b[0] = -1

当m = 1时 依据border算法 b[1]  = 0

....

最后结果应为:其中border(x) = b[m] = b[8] = 3。

 

-1

0

0

1

1

2

3

2

3

 

运行结果和预测一致,如图：问题over！

 

 

 

评论

1 楼 viMory 2008-05-04  

还是搞错了，两个算法有点相似，但还是有着本质的不同，边界问题只关系到一个字符串，KMP算法关系到二个，这怎么可能相同呢？唉，太弱智了...
现在也不得不佩服border算法的精妙