锐客网

  1. 首页 > 睿知 > it技术 > >

字符串匹配介绍

字符串匹配算法也称为“字符串搜索算法”。这是一类至关重要的字符串算法, 其声明为“这是一种在较大的字符串中找到多个字符串的地方的方法”。
【字符串匹配介绍】给定n个字符的文本数组T [1 … .. n]和m个字符的模式数组P [1 … m]。问题在于找到一个整数s, 称为有效移位, 其中0≤s < n-m且T [s + 1 … s + m] = P [1 … m]。换句话说, 即使在T中找到P, 也就是P都是T的子串。P和T的项是从诸如{0, 1}或{A, B … ..Z, a, b … .. z}。
给定字符串T [1 … … n], 对于0≤i≤j≤n-1的子字符串表示为T [i … … j], 该字符串由从索引i到索引j（含）的T。字符串是其自身的子字符串的过程（取i = 0和j = m）。
对于某些0 < i≤j≤n-1, 字符串T [1 … n]的正确子字符串是T [1 … j]。也就是说, 我们必须让i> 0或j < m-1。
使用这些描述, 我们可以说给定任何字符串T [1 … … n], 子字符串为

T [i.....j] = T [i] T [i +1] T [i+2]......T [j] for some 0≤i ≤ j≤n-1.

正确的子字符串是
T [i.....j] = T [i] T [i +1] T [i+2]......T [j] for some 0≤i ≤ j≤n-1.

注意：如果i> j, 则T [i … .. j]等于空字符串或null, 长度为零。用于字符串匹配的算法有不同类型的方法用于查找字符串
  1. 天真的字符串匹配算法
  2. 拉宾·卡普算法
  3. 有限自动机
  4. Knuth-Morris-Pratt算法
  5. Boyer-Moore算法

    推荐阅读


    上一篇：旅行推销员问题

    下一篇：朴素字符串匹配算法