KMP算法之 awk

yinyuemi

简单地实现了KMP的算法，有待优化完善，有精力的童鞋们继续～

1. # KMP algorithm
   
2. 
   
3. function buildindex(s){
   
4.   L=split(s,arr,"")
   
5.   ind[1] = 0
   
6.   for(i = 2; i <= L; i++){
   
7.     for(j=1;j<=L;j++){
   
8.       if(arr[i] ==  arr[j]){
   
9.         ind[i] = 1
   
10.         for(k=1;k<=L-j;k++){
    
11.                    if(arr[k+i] == arr[j+k] && j+k <= L){
    
12.                       ind[i+k] = ind[i+k-1] + 1
    
13.                    }else{
    
14.                       i+=k-1
    
15.                           j=k=L+1
    
16.                    }       
    
17.                 }
    
18.       }else{
    
19.             ind[i] = 0
    
20.                 j=L+1
    
21.           }
    
22.     }
    
23.   }
    
24.   #for(i = 1; i <= L; i++)
    
25.   #print arr[i],ind[i]
    
26. }
    
27. function kmp(string,text){
    
28.   print "string:\t"string
    
29.   print "text:\t"text
    
30.   Len_s = split(string,arr_s,"")
    
31.   Len_text = split(text,arr_text,"")
    
32.   for(i=1; i<=Len_text; i++){
    
33.     for(j=1;j<=Len_s;j++){
    
34.           if(arr_s[j] == arr_text[i]){
    
35.             for(k=1;k<=Len_s-1;k++){
    
36.                   if(arr_s[j+k] != arr_text[i+k]){
    
37.                     i = i+(k-ind[k])
    
38.             j = k = Len_s + 1
    
39.                   }
    
40.                 }
    
41.                 if(k == Len_s){
    
42.                    print "MATCHED!!!"
    
43.                    printf ("%s\033[31;1m%s\033[0m%s",substr(text,1,i-1),substr(text,i,Len_s),substr(text,i+1))
    
44.                    exit
    
45.                 }
    
46.           }else{
    
47.             j = Len_s
    
48.           }
    
49.         }
    
50.   }
    
51.   print "NOT MATCHED!!!"
    
52. }
    
53. BEGIN{
    
54.   text_string = "BBC ABCDAB ABCDABDDABDE"
    
55.   searcing_string = "ABCDABD"
    
56.   buildindex(searcing_string)
    
57.   kmp(searcing_string,text_string)
    
58. }
    

复制代码

awk -f kmp.awk
string: ABCDABD
text:   BBC ABCDAB ABCDABDDABDE
MATCHED!!!
BBC ABCDAB ABCDABDBCDABDDABDE

liion631818

大神。。。。

jason680

modified buildindex function

function buildindex(s){
  Len = split(s, arr, "")
  for(n = 1; n <= Len; ++n){
    ind[n] = 0
    if(n == ind[n-1] + 1) continue
    if(arr[n] == arr[ind[n-1]+1])
      ind[n] = ind[n-1] + 1
    if(ind[n] == 0){
      for(c=1 ; c<=ind[n-1]; ++c){
         if(substr(s,1,c) == substr(s,n-c+1,c))
           ind[n] = c
      }
    }
  }
  #for(n = 1; n <= Len; ++n){
  #  str_a = sprintf("%s%2s", str_a, arr[n])
  #  str_i = sprintf("%s%2d", str_i, ind[n])
  #}
  #print str_a "\n" str_i
}

expert1

膜拜各位大牛，真忘了KMP的东西了。

yinyuemi

回复 3# jason680


    多谢多谢～
   根据你代码，如果我没有理解错的话，还可以进一步优化，如下

modified buildindex function

function buildindex(s){
  Len = split(s, arr, "")
  ind[1] = 0
  for(n = 2; n <= Len; ++n){ # 从2开始
    ind[n] = 0
    if(n == ind[n-1] + 1) continue #这行还可以去掉
    if(arr[n] == arr[ind[n-1]+1])
      ind[n] = ind[n-1] + 1
    if(ind[n] == 0){
      for(c=1 ; c<=ind[n-1]; ++c){
         if(substr(s,1,c) == substr(s,n-c+1,c))
           ind[n] = c
      }
    }
  }
  #for(n = 1; n <= Len; ++n){
  #  str_a = sprintf("%s%2s", str_a, arr[n])
  #  str_i = sprintf("%s%2d", str_i, ind[n])
  #}
  #print str_a "\n" str_i
}

jason680

@yinyuemi @expert1

http://blog.csdn.net/v_july_v/article/details/7041827

Sunday > BM > KMP

reyleon

报告老湿, 我看不懂