字符串匹配 - Overview

字符串匹配(String Matchiing)也称字符串搜索(String Searching)是字符串算法中重要的一种,是指从一个大字符串或文本中找到模式串出现的位置。

字符串匹配概念

字符串匹配问题的形式定义:

  • 文本(Text)是一个长度为 n 的数组 T[1..n];
  • 模式(Pattern)是一个长度为 m 且 m≤n 的数组 P[1..m];
  • T 和 P 中的元素都属于有限的字母表 Σ 表;
  • 如果 0≤s≤n-m,并且 T[s+1..s+m] = P[1..m],即对 1≤j≤m,有 T[s+j] = P[j],则说模式 P 在文本 T 中出现且位移为 s,且称 s 是一个有效位移(Valid Shift)。

比如上图中,目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。该模式在此文本中仅出现一次,即在位移 s = 3 处,位移 s = 3 是有效位移。

字符串匹配算法通常分为两个步骤:预处理(Preprocessing)和匹配(Matching)。所以算法的总运行时间为预处理和匹配的时间的总和。

上图描述了常见字符串匹配算法的预处理和匹配时间。

字符串匹配算法

解决字符串匹配的算法包括:朴素算法(Naive Algorithm) 即暴力破解、Rabin-Karp 算法有限自动机算法(Finite Automation)Knuth-Morris-Pratt 算法(即 KMP Algorithm)Boyer-Moore 算法Simon 算法Colussi 算法Galil-Giancarlo 算法Apostolico-Crochemore 算法Horspool 算法Sunday 算法等。

联系我

添加@pdai微信

PS:添加时请备注Java全栈,谢谢!