是什么

ACDoubleArrayTrie = KMP + DoubleArrayTrie

KMP

• 空间换时间
• 根据模式串 pattern 构建一个跳转指示索引，从而使遍历串的时候“不走回头路”
• 只能匹配单个模式串

Trie：不多说

DoubleArray：把 Trie 以 Array 的形式表达，从而提升性能、降低索引成本。

DoubleArrayTrie

KMP

三个作者（D.E.Knuth、J.H.Morris和V.R.Pratt）

是一种深度优化过的字符串匹配算法

• 时间复杂度为 O(M+N)
• 关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数

两种类型

• 精确匹配
• 近似匹配

本文用 pat 表示模式串，长度为 M，txt 表示文本串，长度为 N。 KMP 算法的任务是在 txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。

dp[j][c] = next
0 <= j < M，代表当前的状态
0 <= c < 256，代表遇到的字符（ASCII 码）
0 <= next <= M，代表下一个状态

dp[4]['A'] = 3 表示：
当前是状态 4，如果遇到字符 A，
pat 应该转移到状态 3

dp[1]['B'] = 2 表示：
当前是状态 1，如果遇到字符 B，
pat 应该转移到状态 2

暴力匹配

特点

• 时间复杂度为 O(MN)，空间复杂度为 O(1)
• 如果字符串中重复的字符比较多，该算法就显得很蠢。

fn brute_force_search(s: &[u8], p: &[u8]) -> Option<usize> {
    let n = s.len();
    let m = p.len();

    if m == 0 { return Some(0); }
    if m > n { return None; }

    for i in 0..=(n - m) {
        for j in 0..m {
            if s[i + j] != p[j] {
                break;
            }
            if j == m - 1 {
                return Some(i);
            }
        }
    }
    None
}

fn main() {
    let s = "hello world";
    let p = "world";
    let res = brute_force_search(s.as_bytes(), p.as_bytes());
    println!("{:?}", res);
}

KMP

KMP 会花费空间来记录一些信息，在以下两种情况下很聪明

KMP 算法永不回退 txt 的指针 i，不走回头路（不会重复扫描 txt），而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配，时间复杂度 O(N)，用空间换时间。它还可以被看成一种动态规划算法。

• 如何计算 dp 呢？ 经过分析，这个 dp 数组，只和 pat 有关

KMP-dp版

正经的 KMP 用的是一维的 next 数组，这里为了代码可读性，用二维的 dp 数组

class KMP:
    def __init__(self, pat: str):
        # 构建 kmp
        # O(m)
        self.pat = pat
        m = len(pat)
        dp = [[0 for _ in range(256)] for _ in range(m)]

        # base case，遇到 pat[0] 才转移 0 -> 1，遇到其它字符停留在 0
        dp[0][ord(pat[0])] = 1

        # x 是影子状态
        x = 0
        for j in range(1, m):
            for c in range(256):
                if ord(pat[j]) == c:
                    dp[j][c] = j + 1
                else:
                    dp[j][c] = dp[x][c]

            x = dp[x][ord(pat[j])]

        self.dp = dp

    def search(self, txt):
        m, n = len(self.pat), len(txt)

        j = 0
        for i in range(n):
            j = self.dp[j][ord(txt[i])]
            if j == m:
                return i - m + 1

        return -1


kmp = KMP('aaab')

kmp.search('aaacaaab')

仿照 Python 版本，写出 Rust 版本：

pub struct KMP {
    dp: Vec<Vec<usize>>,
}

impl KMP {
    pub fn new(pat: &[u8]) -> Self {
        let m = pat.len();
        let mut dp = vec![vec![0; 256]; m];

        for (j, chr) in pat.iter().enumerate() {
            if j == 0 {
                dp[0][*chr as usize] = j + 1;
                continue;
            }
            for c in 0usize..256 {
                if *chr as usize == c {
                    dp[j][c] = j + 1;
                } else { dp[j][c] = dp[j - 1][c] }
            }
        }

        Self { dp }
    }
    pub fn search(&self, s: &[u8]) -> Option<usize> {
        let m = self.dp.len();
        let mut j = 0;

        for (i,chr) in s.iter().enumerate(){
            j = self.dp[j][*chr as usize];
            if j == m {
                return Some(i + 1 - m);
            }
        }

        return None;
    }
}


fn main() {
    let kmp = KMP::new("world".as_bytes());
    let res = kmp.search("hello world".as_bytes());
    let res = kmp.search("hello worll world".as_bytes());
    println!("{:?}", res);

    let kmp = KMP::new("abcac".as_bytes());

    assert_eq!(kmp.search("ababcabcacbab".as_bytes()), Some(5));
    assert_eq!(kmp.search("abcac".as_bytes()), Some(0));
    assert_eq!(kmp.search("abcac14123".as_bytes()), Some(0));
    assert_eq!(kmp.search("ababcabcac".as_bytes()), Some(5));
    assert_eq!(kmp.search("ababcab1cacbab".as_bytes()), None);
}

KMP-next数组

Rust 版本

pub struct KMP {
    pat: Vec<u8>,
    next: Vec<usize>,
}

impl KMP {
    pub fn new(pat: &[u8]) -> Self {
        let mut next = vec![0; pat.len() + 1];
        let (mut i, mut j) = (1, 0);
        while i < pat.len() {
            if j == 0 || pat[i - 1] == pat[j - 1] {
                i += 1;
                j += 1;
                next[i] = j;
            } else { j = next[j] }
        }
        Self { pat: pat.to_vec(), next }
    }
    pub fn search(&self, s: &[u8]) -> Option<usize> {
        let (mut i, mut j) = (1, 1);
        while i <= s.len() && j <= self.pat.len() {
            if j == 0 || s[i - 1] == self.pat[j - 1] {
                i += 1;
                j += 1;
            } else { j = self.next[j]; }
        }
        if j > self.pat.len() {
            return Some(i - j);
        }
        None
    }
}


fn main() {
    let kmp = KMP::new("world".as_bytes());
    let res = kmp.search("hello world".as_bytes());
    let res = kmp.search("hello worll world".as_bytes());
    println!("{:?}", res);

    let kmp = KMP::new("abcac".as_bytes());

    assert_eq!(kmp.search("ababcabcacbab".as_bytes()), Some(5));
    assert_eq!(kmp.search("abcac".as_bytes()), Some(0));
    assert_eq!(kmp.search("abcac14123".as_bytes()), Some(0));
    assert_eq!(kmp.search("ababcabcac".as_bytes()), Some(5));
    assert_eq!(kmp.search("ababcab1cacbab".as_bytes()), None);
}

另外，C/Java/Python 版本放到 gist 了：https://gist.github.com/guofei9987/704b6a946a649812718d008ddab0acfa

ACDoubleArrayTrie

C++/C/Python 实现放到了 gist 了：https://gist.github.com/guofei9987/7f84db7cce1922388a87b7539f578cad

参考文献

• KMP详解：https://zhuanlan.zhihu.com/p/83334559
• AC 自动机：https://www.bilibili.com/video/BV1uJ411Y7Eg