Perl算法实例——朴素字符串匹配算法

我们在文本处理的过程中， 经常需要在特定文本中， 找到指定文本的位置， 或者确定某个字符串是否在特定文本中出现。

这样的操作， 在perl中一般直接可以使用substr方法或者正则来处理， Perl已经帮我包装好了。

今天我们自己来根据朴素字符串匹配方法来实现字符串查找的功能。

朴素字符串匹配算法就是通过一个循环依次增加偏移量，来确定整个字符串的偏移量，从而确定字符串的具体位置。

具体实现如下：

先定义字符串， 然后将字符串切割成字符数组：

my $long_str = 'hello,easyperl,hello world';
my $str      = 'easyperl';


my @long_str_chars = split '', $long_str;
my @str_chars      = split '', $str;

这边我们设置一个标签量， 用来确定是否匹配

my $flag = -1; 

依次增加偏移量：

OUTER:
for my $index(0..@long_str_chars - @str_chars){

对于每次偏移， 依次比较所有对应字符

如果任何一个不对应， 则跳出该循环， 增加偏移量继续：

  for my $index_in(0..@str_chars - 1){
    next OUTER if $long_str_chars[$index + $index_in] ne $str_chars[$index_in];
  }

如果都匹配， 则返回结果， 改变标签值， 提前结束循环

  print "result: $index\n";
  $flag = 1;
  last OUTER;
}


print "result: not found\n" if $flag == -1;