`
viMory
  • 浏览: 58104 次
  • 性别: Icon_minigender_1
  • 来自: 土卫六
最近访客 更多访客>>
社区版块
存档分类
最新评论

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

阅读更多

        昨天那个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]的定义:

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

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

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

    个字符不等(或者相等但T[k]==T[j])(1k<j)。

     如:T=”abCabCad” next[6]=-1,因T[3]=T[6]

3next[j]=k    意义:模式串T中下标为j的字符,如果j的前面k

     字符与开头的k个字符相等,且T[j] != T[k] 1k<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].1k<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!

 

 

 

4
0
分享到:
评论
1 楼 viMory 2008-05-04  
还是搞错了,两个算法有点相似,但还是有着本质的不同,边界问题只关系到一个字符串,KMP算法关系到二个,这怎么可能相同呢?唉,太弱智了...
现在也不得不佩服border算法的精妙

相关推荐

Global site tag (gtag.js) - Google Analytics