Question

运用位移来处理字串匹配问题

http://www-igm.univ-mlv.fr/~lecroq/string/index.html

String Matching

中译“字串匹配”。两个字串 T 和 P，找出 T 当中是否有一段字串正好是 P，并且找出位置。

注：字串匹配当中，我们通常将两字串的象徵符号取做 T 和 P，T 意指 text，P 意指 pattern。可以想作是从长篇文字 T 之中搜索小段文字 P。

T: ababcabc
P: abc

ababcabc    ababcabc
  |||            |||
  abc            abc

T 中有两个地方出现 P。

最直觉的演算法就是穷举法：挪动 P，对准 T 的各个位置；逐一比对字元、判断是否相等。时间複杂度为 O(T * P)。

T: ababcabc
P: abc

0.         1.         2.         3.         4.         5.
ababcabc   ababcabc   ababcabc   ababcabc   ababcabc   ababcabc
|||         |||         |||         |||         |||         |||
abc         abc         abc         abc         abc         abc
(X)         (X)         (O)         (X)         (X)         (O)

String Matching: Morris-Pratt Algorithm

© 2010 tkcn . All rights reserved.

想法

1.
T: aabzabzabcz
P: abzabc

2.
穷举法，从左往右逐步挪动 P。

  aabzabzabcz   aabzabzabcz   aabzabzabcz
  ||||||         ||||||         ||||||      ......
  abzabc         abzabc         abzabc
      (X)           (X)           (X)

2.
仔细看穷举法，是从左往右一一比对字元，一旦发现字元不同，就马上往右挪动 P。

  V              V            V              V        
  aabzabzabcz   aabzabzabcz  aabzabzabcz   aabzabzabcz
  |             |X            |             ||        
  abzabc        abzabc        abzabc        abzabc    

     V             V               V             V    
  aabzabzabcz  aabzabzabcz   aabzabzabcz   aabzabzabcz
   |||          ||||          |||||         |||||X    
   abzabc       abzabc        abzabc        abzabc    

    V             V              V              V     
  aabzabzabcz  aabzabzabcz   aabzabzabcz   aabzabzabcz
    X             X              |             ||       ......
    abzabc        abzabc         abzabc        abzabc 

3.
往右挪动 P 之前，当下比对成功的字串片段，abzab，其实可以好好利用！

         V
   aabzabzabcz    -abzab-----
    |||||X         |||||
    abzabc         abzab-

4.
观察穷举法的步骤顺序，继续往右挪动 P，挪动一个位置、挪动两个位置、……。

  -abzab-----   -abzab-----   -abzab-----
    ||||           |||            ||     
    abzab-         abzab-         abzab- 

   -abzab-----   -abzab-----
        |                   
        abzab-         abzab-

5.
换个角度观察上述行为。
挪动一个位置：看看 abzab 的后四个字元，是不是前四个字元。
挪动两个位置：看看 abzab 的后三个字元，是不是前三个字元。
　　　⋮　　　　　　　　　⋮　　　　　　　　　　⋮

6.
如果我们预先知道 abzab 的“次长的相同前缀后缀”是 ab，
就可以一口气大幅挪动 P，略过许多步骤：

        V                 V
  aabzabzabcz        aabzabzabcz
   |||||X      --->      ||
   abzabc                abzabc

7.
从“V”处继续向右一一比对字元。
每当比对失败、遇到相异字元，
就故技重施，从当前比对成功的字串片段，取其“次长的相同前缀后缀”，大幅挪动 P。

prefix-suffix【尚无正式名称】

前缀等于后缀，称作“相同前缀后缀”。一个字串通常有许多个“相同前缀后缀”。

         prefix-suffix
abc     --------------> {Ø, abc}
abcaa   --------------> {Ø, a, abcaa}
abcabc  --------------> {Ø, abc, abcabc}
ababa   --------------> {Ø, a, aba, ababa}
aaaaa   --------------> {Ø, a, aa, aaa, aaaa, aaaaa}
abaabaa --------------> {Ø, a, abaa, abaabaa}
abzab   --------------> {Ø, ab, abzab}

longest proper prefix-suffix（border）

一个字串的“最长的相同前缀后缀”就是原字串，“最短的相同前缀后缀”就是空字串，“次长的相同前缀后缀”就是第二长的相同前缀后缀。

         border
abc     -------> Ø
abcaa   -------> a
abcabc  -------> abc
ababa   -------> aba
aaaaa   -------> aaaa
abaabaa -------> abaa
abzab   -------> ab

failure function（prefix function）（border function）

穷举法的过程当中，当前比对成功的字串片段，是 P 的前缀。因为我们无法预测是 P 的哪几个前缀，所以我们可以预先计算 P 的每一个前缀的“次长的相同前缀后缀”，以备不时之需！

failure function 是一个字串函数：输入字串的其中一个前缀，则输出该前缀的“次长的相同前缀后缀”。

012345
abzabc

prefix | border |failure function| implementation
-------|--------|----------------|----------------
Ø      | Ø      | f(Ø)      = Ø  | 
a      | Ø      | f(a)      = Ø  | failure[0] = -1
ab     | Ø      | f(ab)     = Ø  | failure[1] = -1
abz    | Ø      | f(abz)    = Ø  | failure[2] = -1
abza   | a      | f(abza)   = a  | failure[3] =  0
abzab  | ab     | f(abzab)  = ab | failure[4] =  1
abzabc | Ø      | f(abzabc) = Ø  | failure[5] = -1

计算 failure function，一般是利用 Dynamic Programming。分割问题的方式，是 P[0...i]拿掉尾端字元 P[i]，利用已知的“次长的相同前缀后缀”，得到 P[0...i]的“次长的相同前缀后缀”。

【待补图片】

称作 failure function，是因为比对失败时，就会使用它。称作 prefix function，是因为此函数的定义域是 prefix。称作 border function，是因为此函数的值域是 border。

字串匹配

字串匹配的过程，跟 failure function 的计算过程十分相像。

一、预先计算 P 的每种前缀的“次长的相同前缀后缀”。
二、从左往右，依序比对字元。
　回、当比对成功、遇到相同字元：
　　　继续比对下个字元。
　回、当比对失败、遇到相异字元：
　　　就从比对成功的字串片段，取其“次长的相同前缀后缀”来大幅挪动 P。
　回、当全部比对成功、匹配到 P：
　　　就从比对成功的 P，取其“次长的相同前缀后缀”来大幅挪动 P。

也来个流程图的版本。

甲、移动“V”。
　　（下一步为乙。）
乙、比对两字元。
　　（若相同，下一步为甲或戊。若不同，下一步为丙。）
丙、从目前比对成功的字串片段，找到“次长的相同前缀后缀”。
　　（下一步为丁。）
丁、向右挪动 P，左端仅露出一截“次长的相同前缀后缀”。
　　（下一步是乙。）
戊、整个 P 匹配成功。
　　（下几步是丙、丁、甲。）
　　（当字串结尾附有'\0'，则下一步是甲。）

时间複杂度：multipop stack 的均摊分析

在讲解时间複杂度之前，先讨论一个基础问题。

有一个 stack，一开始是空的。它有三种操作。

1. push(x)      - worst time O(1)
2. pop()        - worst time O(1)
3. multipop(k)  - 连续 pop 出 k 个元素，如果 stack 是空的就马上停止。
                  worst time O(min(k, s))，当 stack 恰有 s 个元素的时候。

请问这个 stack 进行 N 次操作的时间複杂度为多少？
我们不知道每次的操作是哪一种。可能是三种其中一种。

甲、普通的分析：

乍看之下，花费最多时间的就是 multipop，于是我们就以 multipop 的观点来计算时间複杂度。

一次 multipop 的时间複杂度是 O(min(n, k))，n 是 stack 当下的元素个数，k 是欲 pop 的元素个数；由于 n 和 k 最大可到 N，所以写成 O(N)。

multipop 最多有 N 次，N 次的 multipop 是 O(N^2)，因此时间複杂度就是 O(N^2)。

乙、均摊分析：

N 次操作，stack 从头到尾最多只能放入 N 个元素，也就是 N 次 push。

也就是说，stack 从头到尾最多只能弹出 N 个元素。无论是 pop、multipop，最多只能弹出 N 个元素。

由放入的元素、弹出的元素的总数量，来计算时间複杂度；这两个数量相加最多就是 N，因此时间複杂度就是 O(N)。

时间複杂度

接著回到 Morris-Pratt Algorithm。分为两部分讨论。

甲、进行字串匹配的过程：

以字元两两比对的总次数，作为时间複杂度。

当下比对成功的字串片段 S，想成是 stack 的元素。一开始 S 长度是零；如果比对到相同字元，S 就会增加一字元，想成是 push；如果比对到不同字元，大幅挪动 P 之后，S 就只剩下“次长的相同前缀后缀”，一瞬间变短很多，想成是 multipop。（实际上，一瞬间变短很多只需要 O(1)，时间複杂度远比 multipop 来的小。）

最多有 T 个字元放入 S、弹出 S，所以字元两两比对的总次数不超过 2*T 次。

换个方式说。对于 T 的某一个字元来说，与其他字元进行比对的次数，小于等于“当下比对成功的字串片段”的长度。“当下比对成功的字串片段”是动态改变的，如同 stack 一样增减，所以字元两两比对的总次数不超过 2*T 次。

乙、计算 P 的 failure function 的过程：

原理与甲相同，字元两两比对的总次数不超过 2*P 次。

总时间複杂度为 O(T + P)。

UVa 455 10298 11475

Morris-Pratt Automaton

此演算法可以化作自动机，转化的时间複杂度为 O(PA)，A 为字元种类数目。

化作自动机之后，字串匹配的过程就变得更简单了，甚至可以设计成电子迴路。

转化的原理，是针对每个状态，都找出经由 failure function 能到达的状态们，然后建立转移边，连到那些状态们的下一个状态。

【待补程式码】

ICPC 4842

String Matching: Knuth-Morris-Pratt Algorithm

演算法

          v
T: aaaabcacab
P:    abcabcacab
          ^

Morris-Pratt Algorithm 当中，当比对到上图之处，c != b，所以需要向右挪动 P。找到 abca 的“次长的相同前缀后缀”，也就是 a。然后向右挪动 P，最后左端凸出一段 a，如下图所示。

          v
T: aaaabcacab
P:       abcabcacab
          ^

接下来就继续比对字元。在这裡 c != b，所以又要挪动 P 了。

Knuth 则是多想了一步：连续挪动 P，能不能预先侦测呢？Knuth 发现，找到 abca 的“次长的相同前缀后缀”a 之后，看看 a 的下一个字元（是 b），是否仍是 abca 的下一个字元（也是 b）。如果两个字元一样的话，那就表示 P 铁定会连续挪动两次，两次比较都是 c != b。

既然铁定会挪动两次，那乾脆直接移到定位不就好了？于是 Knuth 在计算 failure function 的时候，就额外加了一个判断：找到 abca 的相同前缀后缀 f(abca) = a 之后，如果 f(abca) 的下一个字元恰巧仍是 abca 的下一个字元，那麽就令 f(abca) = f(a)，也就是再多找一次 a 的相同前缀后缀。如此一来，P 只要移一次就行了。

由于是用递迴定义 failure function，所以连续挪动三次、四次、五次的情况，经过递迴计算，最后都会变成一次移到定位。

延迟时间

当 T 是一个 stream I/O、读入字元只能一个一个来的情况下，每读入一个字元最多会有 1+log_φP 次字元比较。换句话说，每读入一个字元，直到需要读取下一个字元前，期间最多会停滞 O(log_φP) 的时间。

【待补证明】

Multi-Pattern String Matching: Aho-Corasick Algorithm

suffix link

【注：原始论文是 failure function 与 output function】

Morris-Pratt Algorithm 的加强版，同时匹配数个 P。预先把所有 P 建立成一棵 trie，每个节点添上 failure function，之后就可以拿 trie 与 T 进行字串匹配了。

Morris-Pratt Algorithm 是找到“当下比对成功的字串片段”的后缀（不含本身），是 P 的哪一个前缀。尽可能长。

Aho-Corasick Algorithm 是找到“当下比对成功的字串片段”的后缀（不含本身），是哪一个 P 的哪一个前缀。尽可能长。

因此，failure function 其实就是寻找 trie 上每个节点的后缀（不含本身），尽可能长。直觉的称呼是 suffix link。

dictionary suffix link

【注：原始论文无此概念。】

当 P 之中无父子关係，比对字元时，当前节点仅需判断是否匹配到 P。

当 P 之中有父子关係（一个字串是另一个字串的子字串、但是不相等），比对字元时，当前节点必须额外行走 suffix link，以找到所有匹配的 P。

添上 dictionary suffix link，以更迅速地找到所有匹配的 P。

           suffix link：不含本身的后缀、尽可能长。
dictionary suffix link：不含本身的后缀、尽可能长、必须是某个 P。

演算法

一、所有 P 建立一棵 trie。
二、添上 suffix link、dictionary suffix link。
三、拿 T 做字串比对：
　回、比对成功、遇到相同字元：走 trie edge。
　回、比对失败、遇到相异字元：走 suffix link。
　回、找到所有匹配的 P：另走 dictionary suffix link。
　　　（若 P 之中无父子关係，
　　　　仅需判断当前节点是否完全比对成功、匹配到 P 即可。）

时间複杂度

建立 trie 的时间複杂度是 O(P1 + ... + Pn) = O(∑(Pi)) = O(P)。

字串匹配的时间複杂度是 O(T + K)，K 是每个 P 在 T 中的出现次数的总和。K 最小为 0，K 最大为 O(T * n)。

【注：原始论文中，字串匹配的时间複杂度是 O(T + P + K)。当数个 T 做字串匹配，将慢许多。】

2D String Matching: Baker-Bird Algorithm

演算法

当 T 与 P 是二维长方形的时候。时间複杂度是 O(T+P)。

1.
把 T 横切成一条一条，
把 P 横切成一条一条，
然后每一条 T 都执行 Multi-Pattern String Matching，例如 Aho-Corasick Algorithm。
如果第 a 条 P，从 T[i,j]开始出现，那麽就进行记录：M[i,j] = a。
M 是一个跟 T 一样大的阵列。

2.
把 M 直切成一条一条，
每一条 M 都执行 String Matching，例如 Morris-Pratt Algorithm。
看看是否出现 1234567...n 这个字串（P 总共 n 条）。

X.
当 P 有某两条相同时，则要小心处理，把这两条的编号设为相同。

附带一提，如果是使用 Aho-Corasick Algorithm，因为 P 中不会有父子关係，所以不必建 dictionary suffix link，省下很多功夫。

UVa 11019 Timus 1486

String Matching: Gusfield's Algorithm（Z Algorithm）

z function

定义一个函数 z()，z(i) 是指由 s[i]开始的字串，与 s[0]开始的字串可以匹配到多长。也就是说 s[0 ... z(i)-1] = s[i ... i+z(i)-1]。

  | 0 1 2 3 4 5 6 7
--+-----------------
s | a b a a b a a b
z | 8 0 1 5 0 1 2 0

z(0)：abaabaab，长度 8。
z(1)：Ø，长度 0。
z(2)：a，长度 1。
z(3)：abaab，长度 5。

设计此函数的缘由，是因为进行字串匹配的时候，我们总是希望两字串的开头尽可能长得一样。至于为什麽取名为 z，就得问原作者了。后面将提到如何运用 z function 作字串匹配，现在先讲解如何计算 z function。

计算 z()，是从左往右算。z(0) 是特例，z(0) 是整个字串的长度，所以 z(0) 不用算，由 z(1) 开始算。

计算 z(i)，是运用已经算好的 z(j)，j < i。也就是指已经算好的某一段 s[0 ... z(j)-1] = s[j ... j+z(j)-1]。首先找出哪一段 s[j ... j+z(j)-1]覆盖了 s[i]，而且 j+z(j)-1 越右边越好。

一、如果没有任何一段 s[j ... j+z(j)-1]覆盖了 s[i]，表示已经算好的部份都派不上用场。从 s[i]与 s[0]开始比对，逐字比下去。

二、如果有一段 s[j ... j+z(j)-1]覆盖了 s[i]，表示 s[i]也会出现在 s[0 ... z(j)-1]之中，把 i 映射到对应的位置 i'。紧接著再来一次，运用 z(i')，也就是指 s[0 .... z(i')-1] = s[i' ... i'+z(i')-1]，如此又把 i'映射到字串开头了。

二之一、如果 s[i ... i+z(i')-1]短少于 s[j ... j+z(j)-1]的右端，那就可以直接算出 z(i) 的答案，就是 z(i')。

二之二、如果 s[i ... i+z(i')-1]刚好贴齐 s[j ... j+z(j)-1]的右端，那就必须检查不确定的部分，直接从 s[j+z(j)]与 s[j+z(j)-i]继续比对，逐字比下去。

二之三、如果 s[i ... i+z(i')-1]凸出了 s[j ... j+z(j)-1]的右端，则与上一种情形相同。

时间複杂度

以字元两两比较的总次数，作为时间複杂度。

j+z(j)-1 这个数值会从 0 开始不断增加。每当字元比对成功时，j+z(j)-1 就会跟著增加，下次比对的时候就会从 j+z(j) 继续比对。j+z(j)-1 这个数值的增加次数与比对次数一样多，最多会从 0 增加到 S，所以时间複杂度是 O(S)。

j 便是原著中的 L，j+z(j)-1 便是原著中的 R。

String Matching: Boyer-Moore Algorithm

演算法

http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

每次向右挪动 P，有著 good-suffix shift 与 bad-character shift 两种挪动选项，选择向右挪动较多者。

每次挪动 P 之后，从 P 的右端、往 P 的左端比对字元。

good-suffix shift

P 的每个后缀，找到本身以外，最后出现的地方。

若没重複出现，则找到“次长的相同前缀后缀”。即是 failure function，定义域变成后缀罢了。

计算 good-suffix shift 表格的时间複杂度为 O(P)。

bad-character shift

P 的每个字元，找到最后出现的地方。

注意到 bad-character shift 可能向左挪动。

计算 bad-character shift 表格的时间複杂度为 O(P + A)。A 为字元种类数目。

时间複杂度

字串比对，最差的时间複杂度为 O(T * P)，此时 T 与 P 的全部字元皆相同；最佳的时间複杂度为 O(T / P)，此时 T 与 P 没有共同的字元。

当 T 与 P 并非週期性字串，字元两两比对最多 3T 次。

号称实务上最快的演算法。

Multi-Pattern String Matching: Wu-Manber Algorithm

大意

硬是拿 Boyer-Moore Algorithm 来做多重字串比对，工程味道浓厚的演算法。

向右挪动 P，只有 bad-character shift 一种挪动选项。

比对单位由一个字元，改为 B 个字元。个人推敲其用意如下：

一、B 取 log_A∑(Pi)，能降低理论上的时间複杂度。

二、过去在 Big5 编码中（现今多採 UTF-8 编码），一个中文字是两个位元组。B 取 2，就能以中文字为比对单位。

三、中文是以字组词。B 加大，就能以词、词组为比对单位。

【注：此演算法的比对单位是 B 个字元，然而挪动单位仍是一个字元。因此二与三是空谈。】

实作时，B 个字元用 hash function 合而为一数。

演算法

一、只看每个 P 的左端 m 个字元，暂时忽略右端其馀字元。
　　P 长度最短者，取作 m。
二、预先建立 SHIFT table、HASH table、PREFIX table。
三、实施 Boyer-Moore Algorithm 的字串匹配演算法，
　　比对单位改为 B 个字元，挪动单位仍是一个字元。
　　直接从 SHIFT table 取值，判断比对成功、比对失败。
　回、B 个字元比对失败：
　　甲、SHIFT table，根据其值，向右挪动 P。
　回、B 个字元比对成功：
　　甲、P 的后缀在 T 中：
　　　　HASH table，得到后缀是这 B 个字元的所有 P。
　　乙、P 的前缀在 T 中：
　　　　PREFIX table，得到这些 P 的前缀、B 个字元，判断是否也在 T 出现。
　　　　T 的当前比对位置往左数 m 个字元，就能进行判断了。
　　丙、P 的其馀片段在 T 中（只有这裡是看 P 的全部字元）：
　　　　逐个字元比对，方向随便。若完整匹配到 P，就输出。
　　丁、向右挪动 P、一个字元。

SHIFT table

输入 B 个字元，找到整个 P 之中最后出现的地方。

时间複杂度是 O(P * B)。

空间複杂度是 O(A ^ B)，A 是字元种类数目。

HASH table

输入后缀、B 个字元，得到符合条件的所有 P。

时间、空间複杂度同 SHIFT table。

PREFIX table

输入其中一个 P，得到前缀、B 个字元。

时间複杂度是 O(n * B)，空间複杂度是 O(n)，n 是 P 的个数。

时间複杂度

字串比对，最差的时间複杂度是 O(BTP)，此时 T 与 P 的全部字元皆相同。最佳的时间複杂度是 O(BT/m)，此时 T 与 P 没有共同的连续 B 个字元。