有没有大神愿意试试把这个perl改成shell脚本呀~

huang6894

逛论坛的时候，学习了Send_linux大大的字符串匹配的KMP算法
http://bbs.chinaunix.net/forum.p ... mp;fromuid=29097174
觉得很有意思，在网上有很多关于C实现的，perl的话：

1. use Data::Dumper;
   
2. 
   
3. my $from = 'abababd ababc';
   
4. my $find = 'ababc';
   
5. 
   
6. # 分隔字符串为array
   
7. my @from = split '', $from;
   
8. my @find = split '', $find;
   
9. 
   
10. print $find, "\n";
    
11. print @{ calc( \@find ) }, "\n";
    
12. print "\n";
    
13. print kmp( \@from, \@find );
    
14. 
    
15. ############################
    
16. # 计算字符串的重复值
    
17. sub calc {
    
18.     my ($array) = @_;
    
19. 
    
20.     # 取与字串相同长度的array 并将第一个置0
    
21.     my @tmp = (@$array);
    
22.     $tmp[0] = 0;
    
23. 
    
24. # 之后的每一个字符都与开头字串比较，取@tmp 前一个值作为比较字符
    
25. # 若为0，前一字符个与开头不重复，比较字符指向开头0
    
26. # 若不为0，前一个字符与开头有重复，如果还相同，@tmp 值加1，否则为0，后继自符重新从头开始比较
    
27.     for ( 1 .. $#tmp ) {
    
28.         if ( $array->[$_] eq $array->[ $tmp[ $_ - 1 ] ] ) {
    
29.             $tmp[$_] = $tmp[ $_ - 1 ] + 1;
    
30.         }
    
31.         else {
    
32.             $tmp[$_] = 0;
    
33.         }
    
34.     }
    
35.     return \@tmp;
    
36. }
    
37. 
    
38. sub kmp {
    
39.     my ( $from, $find ) = @_;
    
40. 
    
41.     # 初始从开头比较
    
42.     my $i   = 0;
    
43.     my $tmp = calc($find);
    
44. 
    
45.     # 剩余字串长度小于搜索字串，则退出返回-1
    
46.     while ( ( $#{$from} - $i ) >= $#{$find} ) {
    
47. 
    
48.         # 观察每次步进长度
    
49.         print @$from[ $i .. $#{$from} ], "\n";
    
50. 
    
51.         # j 标记搜索到的字串长度
    
52.         my $j = 0;
    
53.         while ( $find->[$j] eq $from->[ $i + $j ] ) {
    
54. 
    
55.             # 搜索到的长度与字符串长度相同，说明找到，返回index位置
    
56.             if ( $j == $#{$find} ) {
    
57.                 return $i;
    
58.             }
    
59.             else {
    
60.                 $j++;
    
61.             }
    
62.         }
    
63. 
    
64.         # 有相同的字符串，根据计算的值来跳转多个字符并重新比较
    
65.         # $j 为相同的个数（以1为基数），@tmp[$j-1] 为同开始字符重复的个数
    
66.         if ($j) {
    
67.             $i += $j - $tmp->[ $j - 1 ];
    
68.         }
    
69.         else {
    
70.             $i++;
    
71.         }
    
72.     }
    
73.     return -1;
    
74. }
    

复制代码

输出：

1. #字符串以及计算重复值结果
   
2. ababc
   
3. 00120
   
4. 
   
5. #每次查找过程
   
6. abababd ababc
   
7. ababd ababc
   
8. abd ababc
   
9. d ababc
   
10. ababc
    
11. ababc
    
12. 8

复制代码

求大神shell方案！！哈哈

yinyuemi

回复 1# huang6894

1. 
   
2. from='abababd ababc';
   
3. find='ababc';
   
4. 
   
5. arr_from=($(sed 's/./ "&"/g;s/ //' <<<$from));
   
6. arr_find=($(sed 's/./ "&"/g;s/ //' <<<$find));
   
7. 
   
8. ############################
   
9. # 计算字符串的重复值
   
10. #sub calc {
    
11. function calc_(){
    
12.     array=($*);
    
13.     # 取与字串相同长度的array 并将第一个置0
    
14.     tmp=($*);
    
15.         tmp[0]=0;
    
16.         len=${#tmp[*]};
    
17. # 之后的每一个字符都与开头字串比较，取@tmp 前一个值作为比较字符
    
18. # 若为0，前一字符个与开头不重复，比较字符指向开头0
    
19. # 若不为0，前一个字符与开头有重复，如果还相同，@tmp 值加1，否则为0，后继自符重新从头开始比较
    
20.         for ((i=1;i<=len-1;i++))
    
21.         do       
    
22.                 if [[ ${array[$i]} == ${array[${tmp[$((i-1))]}]} ]]
    
23.                 then
    
24.                         tmp[$i]=$((tmp[i-1]+1));
    
25.                 else
    
26.                         tmp[$i]=0;
    
27.                 fi
    
28.         done
    
29.     echo ${tmp[@]};
    
30. }
    
31. 
    
32. 
    
33. function kmp() {
    
34.     eval from_=("$(sed 's/./ "&"/g;s/ //' <<<$1)");
    
35.         eval find_=("$(sed 's/./ "&"/g;s/ //' <<<$2)");
    
36.         # 初始从开头比较
    
37.         m=0;
    
38.         tmp1=($(eval calc_ "${find_[*]}"));
    
39.         len1=${#find_[*]};
    
40.         len2=${#from_[*]};
    
41.     # 剩余字串长度小于搜索字串，则退出返回-1
    
42.     while(( len2-m >= len1))
    
43.         # 观察每次步进长度
    
44.         do
    
45.                 for((n=m;n<=len2-1;n++))
    
46.                 do
    
47.                         printf ${from_[$n]}
    
48.                 done
    
49.                 printf "\n";
    
50.         # j 标记搜索到的字串长度
    
51.         local j=0;
    
52.                 while [[ ${find_[j]} == ${from_[$((m+j))]} ]]
    
53.                 do
    
54.             # 搜索到的长度与字符串长度相同，说明找到，返回index位置
    
55.             if (( j == len1-1 ))
    
56.                         then
    
57.                                 echo $m;
    
58.                                 return $m;
    
59.             else
    
60.                                 ((j++));
    
61.                         fi
    
62.                 done
    
63.         # 有相同的字符串，根据计算的值来跳转多个字符并重新比较
    
64.         # $j 为相同的个数（以1为基数），@tmp[$j-1] 为同开始字符重复的个数
    
65.                 if ((j>0))
    
66.                 then
    
67.                         m=$((m+j-tmp1[j-1]))
    
68.         else
    
69.                         ((m++));
    
70.                 fi
    
71.         done
    
72. }
    
73. IFS=$'';
    
74. echo $find;
    
75. calc_ ${arr_find[@]};
    
76. kmp $from $find;
    
77. 
    

复制代码

huang6894

回复 2# yinyuemi


    大神啊！！！大神啊~谢谢咯