免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1650 | 回复: 6

[学习共享] KMP算法之 awk [复制链接]

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2016-08-11 09:30 |显示全部楼层
简单地实现了KMP的算法,有待优化完善,有精力的童鞋们继续~
  1. # KMP algorithm

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

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

论坛徽章:
10
天蝎座
日期:2013-09-22 22:32:23程序设计版块每日发帖之星
日期:2016-08-07 06:20:00lufei
日期:2016-06-17 17:38:40程序设计版块每日发帖之星
日期:2016-06-12 06:20:002016科比退役纪念章
日期:2016-05-31 15:47:20CU十四周年纪念徽章
日期:2016-05-27 12:24:562015年亚洲杯之阿曼
日期:2015-05-03 21:01:352015年辞旧岁徽章
日期:2015-03-03 16:54:15天蝎座
日期:2013-10-20 21:05:24程序设计版块每日发帖之星
日期:2016-08-11 06:20:00
发表于 2016-08-11 09:34 |显示全部楼层
大神。。。。

论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
发表于 2016-08-11 16:36 |显示全部楼层
本帖最后由 jason680 于 2016-08-12 08:09 编辑

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
}



论坛徽章:
16
IT运维版块每日发帖之星
日期:2015-08-24 06:20:00综合交流区版块每日发帖之星
日期:2015-10-14 06:20:00IT运维版块每日发帖之星
日期:2015-10-25 06:20:00IT运维版块每日发帖之星
日期:2015-11-06 06:20:00IT运维版块每日发帖之星
日期:2015-12-10 06:20:00平安夜徽章
日期:2015-12-26 00:06:302016猴年福章徽章
日期:2016-02-18 15:30:34IT运维版块每日发帖之星
日期:2016-04-15 06:20:00IT运维版块每日发帖之星
日期:2016-05-21 06:20:00综合交流区版块每日发帖之星
日期:2016-08-16 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-14 06:20:00
发表于 2016-08-12 13:37 |显示全部楼层
膜拜各位大牛,真忘了KMP的东西了。

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2016-08-12 13:57 |显示全部楼层
本帖最后由 yinyuemi 于 2016-08-12 13:58 编辑

回复 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
}

论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
发表于 2016-08-12 14:30 |显示全部楼层

论坛徽章:
60
20周年集字徽章-20	
日期:2020-10-28 14:04:3015-16赛季CBA联赛之北京
日期:2016-07-06 15:42:0715-16赛季CBA联赛之同曦
日期:2016-06-12 10:38:0915-16赛季CBA联赛之佛山
日期:2016-05-27 11:54:56黄金圣斗士
日期:2015-12-02 11:44:35白银圣斗士
日期:2015-11-25 14:32:43白银圣斗士
日期:2015-11-23 12:53:352015亚冠之布里斯班狮吼
日期:2015-10-21 16:55:482015亚冠之首尔
日期:2015-09-01 16:46:052015亚冠之德黑兰石油
日期:2015-08-31 11:39:192015亚冠之萨济拖拉机
日期:2015-08-28 21:06:5315-16赛季CBA联赛之广东
日期:2016-07-12 14:58:53
发表于 2016-08-12 15:39 |显示全部楼层
报告老湿, 我看不懂
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP