字符串匹配

algorithm

最近在复习一些基础算法，正好把字符串匹配的各种知识总结记录一下。关于字符串匹配我们都不陌生，例如 ruby 中 String 的 index 等一系列方法。下面先说一下最简单粗暴的解法。

先分解下问题，现在我们要解决的问题可以简单描述为这样：现有一字符串 S ，现查找目标字符串 P 在 S 中的位置。

暴力解法

所谓暴力法就是逐字符便利匹配字符串具体过程是这样的：
1. 从头部开始逐字符匹配 S 与 P，设置指针 i 指向 S 头部
2. 如果遇到字符不匹配，则令指针 i 向后移，并重头开始匹配 P
3. 重复第二步，直至成功匹配或者失配

举个简单的例子：
现有字符串 S ： 'acdfcacdchd' , 现查找目标字符串 P： 'acdc'在 S 中的位置。其匹配过程是这样的：
1. 首先 S[0] 与 P[0] 比较，发现匹配，继续向后匹配 S[1] 和 P[1]
2. 直至匹配到 S[3] 与 P[3] 时，发现不匹配。向后移从 S[1] 开始匹配 P
3. 发现 S[1] 与 P[0] 不匹配，继续后移从 S[2] 开始
4. （重复过程略）
5. 发现 S[5] 与 P[0] 匹配，各自向后移一位，继续向后匹配 S[6] 和 P[1]
6. 最终完成匹配

说起来挺啰嗦，其实就是循环匹配的过程，实现起来很简单：

def method_one
  i = j = 0
  while i < @a_length && j < @p_length
    if @string_a[i] == @string_p[j]
      i += 1
      j += 1
    else
      i = i - j + 1
      j = 0
    end
  end
  # matching complete
  if j == @p_length
    i - j
  else
    -1
  end
end

或者下面这种写法更容易看明白，还可以通过适当剪枝来减少循环数：

def method_two
  res = -1
  (0..(@a_length - @p_length)).each do |i|
    (0..(@p_length-1)).each do |j|
      break if @string_a[i + j] != @string_p[j]
      return i if j == @p_length - 1
    end
  end
  res
end

经典的 KMP 算法叙述起来可能会比较繁复，就暂且再研究研究放在下次记述了。