字符匹配算法

  • BF算法
  • KMP算法

先在开头约定

文中原始待匹配串为text，如“ababcabc”
匹配串为pattern，如“ababc”
最长前后缀数组为prefix table[ ]

BF算法概述

  1. BF算法属于暴力匹配算法，时间复杂度在O(mn)，较为耗时间。
  2. 其原理在于从头遍历text串，当text中某字符与pattern中第一个相等时，继续将指向text的下标值(i)向后移，同时将指向pattern的下标值(j)向后移
  3. 当出现text和pattern对应字符不相等时，将i回溯至上一次开始匹配的位置的下一位，将j回溯到0的位置，重复执行此操作。
  4. 当pattern被j遍历结束的时候，则表明匹配成功；当text被遍历结束的时候，则表明匹配失败，在text中未找到pattern。

BF算法较为简单，这里不做详细介绍。

KMP算法介绍

最长公共前后缀(prefix table)

假设pattern=“ababca”，则如下图：
则形成一个prefix数组，prefix[ ]={0,0,2,2,0,1}，在KMP算法中，为便于算法书写，将最后一位删除，在第一位补-1，则形成prefix[ ]={-1，0，0，2，2，0}。prefix数组的作用下文将详细给出。