0010 - Regular Expression Matching

Other

July 21, 2023

题干

破题

这道题令人有些五味杂陈，说它是一道不好的题有它不好的理由，说它是一道好的题有好的理由，它好还是不好可能取决于你做题的流程。

不好的说，这道题并不是那种抽象得非常干净的题目，它更像是现实中的问题，有开放式的解决方法，可能涉及多方面知识，主要时间需要用在考虑核心算法无关的处理细节。作为那种习惯性地先成功提交，然后才回去看解析和答案的人来说这种题是非常煎熬的而且花费时间的，除非你已经很熟悉了这个套路¹²。

好的说，如果你实现就清楚这个套路，做过类似的题目，那么标准答案至少在形式上也是很简洁的³

另外，当看到文本串与模式串的长度都不超过 $20$ 的条件时，就可以想到，不管这道题的本意如何，标准解法是什么，几乎一定存在一种自然解法，性能不劣于标准解法。⁴

Tips：

题目保证了 * 字符前面一定会有一个合法的字符，否则我们还需要检查下模式串的合法性。

解①固定串匹配：

基于固定串匹配的自然解法

这是我的自然解法，考虑得并不是标准解法里的字符匹配的模型⁵，而是考虑模式匹配或者子串匹配的思路，这也应该是初学者自然的思路。

模式串里有两种模式匹配，一种是长度固定的串，就是所有普通字符加上 . 符号，匹配这种长度固定的串是很容易的，可以用如下的方法：

#[inline]
fn match_pat(s: &[u8], pat: &[u8]) -> bool {
    s.len() == pat.len()
        && s.iter()
            .zip(pat.iter())
            .all(|(&c1, &c2)| c2 == '.' as u8 || c2 == c1)
}

另一种是长度不定的串，就是后面带 * 字符的双字符串，像 .* , a* 等等，长度不定的串的匹配是问题的难度所在，或者也是时间复杂度飙升的地方。

于是我们的思路就很清楚，首先匹配掉固定串，然后再用回溯剪枝的方法检查不定串。

给定文本串 s: String 和模式串 p: String

Step-1：搜索不定串

在模式串上搜索所有不定串的位置

let p_bytes = p.as_bytes();
let s_bytes = s.as_bytes();

let random_pats: Vec<usize> = p
	.match_indices('*')
	.map(|(i, _)| i - 1)
	.collect();

Step-2：划分固定串

划分出模式串中中间的固定串

我们真正关心得应该是夹在不定串之间的那些固定串，因为模式串两端的固定串是可以简单匹配确定的⁶

在搜索固定串的位置之前，需要先检查所有其他的情况：有零个不定串或者一个不定串

零个不定串：

最简单的情况，直接使用固定串的匹配方法即可。

if random_pats.is_empty() {
    return match_pat(s_bytes, p_bytes);
}

一个不定串：

这种情况下，需要做两端固定串的匹配，然后比较文本串两端中间的部分是否匹配这个唯一地不定串。

在做两端固定串的匹配时，首先要检查长度是否匹配，来防止计算头尾固定串时发生算术溢出问题。

// s_bytes head i inclusive
let head = random_pats[0];
let tail_slice = &p_bytes[random_pats.last().unwrap().clone() + 2..];

if p_bytes.len() - 2 * random_pats.len() > s_bytes.len() {
    return false;
}

// s_bytes tail i exclusive
let tail = s_bytes.len() - tail_slice.len();

head 表示头部固定串的长度，也是其余部分的起始位置，tail 表示尾部固定串的起始位置，因此 s_bytes[head..tail] 才是我们真正要做模式匹配的地方。

if !match_pat(&s_bytes[..head], &p_bytes[..head]) {
    return false;
}

if !match_pat(&s_bytes[tail..], tail_slice) {
    return false;
}

/* ONE '*' */

if random_pats.len() == 1 {
    let c = p_bytes[random_pats[0]];

    return if c == '.' as u8 {
        true
    }
    else {
        s_bytes[head..tail].into_iter().all(|&x| x == c)
    };
}

至少两个不定串：

固定串划分就是：

let fixed_pats: Vec<&[u8]> = random_pats
    .iter()
    .skip(1)
    .scan(random_pats[0] + 2, |last_i, &i| {
        let slice = &p_bytes[*last_i..i];
        *last_i = i + 2;
        Some(slice)
    })
    .collect();

Step-3：搜索固定串

在文本串上预搜索所有固定串的位置

比起在文本匹配时动态地搜索每个固定串的位置，不如预先地搜索完所有固定串可能在文本串上出现的位置。

这里还有一个限制，可以用来减少可能性地空间，就是固定串的先后顺序和它们自身的长度，不过在此之前需要先确保整个文本串的空余长度足以容纳所有固定串：

let fixed_pats_tot: usize = fixed_pats.iter().map(|s| s.len()).sum();

if fixed_pats_tot > tail - head {
    return false;
}

用一个嵌套的数组 fixed_pats_pos 来依次保存每个固定串的可能在文本串上的可能位置⁷⁸，如果发现有个固定串没有合适的位置，那就可以提前返回失败了：

let mut start = head;
let mut end: usize = tail - fixed_pats_tot;

let mut fixed_pats_pos = vec![];

for pat in fixed_pats.iter() {
    let pos: Vec<usize> = (start..=end)
    	.filter(|&j| match_pat(&s_bytes[j..j + pat.len()], pat))
    	.collect();

    if pos.is_empty() {
        return false;
    }

    fixed_pats_pos.push(pos);

    start += pat.len();
    end += pat.len();
}

这里使用了简单地匹配搜索，因为模式和文本都非常地短，如果是其他的情况在串上地多模式搜索，就有 AC 自动机，或者简单高效地 Sunday 算法。

Step-4：回溯剪枝

一般来说回溯剪枝比较简洁的实现形式是递归，不过我习惯性地写非递归的版本，它在 Debug 的时候看得更清楚。

根据不定模式与文本的匹配情况，确定一个对应固定模式的起始范围，遍历这个起始范围，分别收集固定模式的可能位置，然后来到下一级。

让我们澄清一下这个比较方法：首先是前面的不定串，然后是后面的固定串，这样不定串与它后面的固定串两两划分，直到最后一个不定串，对应得是尾部的固定串。

这样一直到尾部的固定串都匹配时，就匹配成功，否则返回上一级，选取下一个可能位置，如果上一级为空，就继续向上返回。

let mut search_stack = vec![vec![head]];
let mut lv = 0;

loop {
    // check fail condition
    while search_stack[lv].is_empty() {
        search_stack.pop();

        if search_stack.is_empty() {
            return false;
        }

        lv -= 1;
    }

    let i = search_stack[lv].pop().unwrap();
    let c = p_bytes[random_pats[lv]];

    let mut scale = 0;

    if c != '.' as u8 {
        for &s_c in &s_bytes[i..] {
            if s_c != c {
                break;
            }

            scale += 1;
        }
    }
    else {
        scale = s_bytes.len() - 1; // big enough
    }

    // check succeed condition
    if lv == fixed_pats_pos.len() {
        if i <= tail && i + scale >= tail {
            return true;
        }
    }
    else {
        let pos: Vec<usize> = fixed_pats_pos[lv]
        .iter()
        .filter(|&&j| j >= i && j <= i + scale)
        .map(|&j| j + fixed_pats[lv].len())
        .collect();

        if !pos.is_empty() {
            search_stack.push(pos);
            lv += 1;
        }
    }
}

至此为止就是原始版本的匹配算法，它的运行时间在 273 ms (beats 10.49%)，可以通过，但还不够好，可以通过一点点改进显著地提高性能。

Step-5：记录失败

可以直观地发现，有大量可以简单避免的无效匹配，如果某级从某个位置开始的后面所有可能匹配都失败了，那么下次再有从这一级的该位置开始的搜索就可以直接跳过。

可以直接用一个全局数组⁹记录失败情况，并用栈追踪级别和位置，以在全局数组上更新：

const MAX_S_LEN: usize = 20;
const MAX_LV: usize = MAX_S_LEN / 2;

static mut FAILED: [bool; MAX_LV * MAX_S_LEN] = [false; MAX_LV * MAX_S_LEN];

// ...

// i, scale
let mut bak_range = vec![(0, 0)];

修改后的回溯版本：

let mut search_stack = vec![vec![head]];
let mut lv = 0;
// i, scale
let mut bak_range = vec![(0, 0)];

unsafe { FAILED.fill(false) };

loop {
    // check fail condition
    while search_stack[lv].is_empty() {
        search_stack.pop();

        if search_stack.is_empty() {
            return false;
        }

        lv -= 1;

        let (i, scale) = bak_range.pop().unwrap();

        let base = lv*MAX_S_LEN + i;
        unsafe { (&mut FAILED[base..=base+scale]).fill(true) }
    }

    let i = search_stack[lv].pop().unwrap();

    if unsafe { FAILED[lv*MAX_S_LEN+i] } {
        continue;
    }

    let c = p_bytes[random_pats[lv]];

    let mut scale = 0;

    if c != '.' as u8 {
        for &s_c in &s_bytes[i..] {
            if s_c != c {
                break;
            }

            scale += 1;
        }
    }
    else {
        scale = s_bytes.len() - 1; // big enough
    }

    // check succeed condition
    if lv == fixed_pats_pos.len() {
        if i <= tail && i + scale >= tail {
            return true;
        }
    }
    else {
        let pos: Vec<usize> = fixed_pats_pos[lv]
        .iter()
        .filter(|&&j| j >= i && j <= i + scale)
        .map(|&j| j + fixed_pats[lv].len())
        .collect();

        if !pos.is_empty() {
            search_stack.push(pos);
            bak_range.push((i, scale));
            lv += 1;
        }
    }
}

如果不计预先搜索固定串的开销¹⁰，那么有失败记录的实现的时间复杂度就是 $O(nm)$ ，与标准实现的一样。

它的运行时间稳定在 $0$ ms，还要优于简单形式的标准实现。

解②DP：

标准实现，不细究地话形式还是很简洁的。

把文本串与模式串逐字符比较，模式串中的不定串前面的字符当做普通字符处理，后面的星号才当做不定串特别处理。

分别用 $i$ 和 $j$ 表示文本串和模式串的匹配的前缀，二维地布尔数组 $\texttt{dp}[i][j]$ 表示 $s[0..i-1]$ 和 $p[0..j-1]$ 是否匹配。

当 $s[i-1] \neq *$ 时，如果 $\texttt{dp}[i-1][j-1]$ 匹配，并且 $s[i-1] = p[i-1]$ ，那么 $\texttt{dp}[i][j]$ 就是匹配的；

当$s[i-1] = *$ 时：

假设这个不定串匹配了零次，此时 $\texttt{dp}[i][j]=\texttt{dp}[i][j-2]$；
假设这个不定串至少匹配了一次，此时 $\texttt{dp}[i][j]=\texttt{dp}[i-1][j] \land s[i-1] = p[i-2]$

最后匹配了整个文本串和模式串的 $i$， $j$ 的 $\texttt{dp}[i][j]$ 就是需要的匹配结果。

另外需要考虑的一点是状态数组的初始状态：

当两个串都是空串时，状态是匹配的；
当其中一个串为空，另一个不为空时，应该是不匹配的，除了一个特殊情况；
特殊情况是，当文本串为空，模式串不为空，但全都是不定串时，比如 a*b*.* 时，也是匹配的

基本实现

假如用文本串作为外循环：

let mut dp = vec![vec![false; p_bytes.len()]; s_bytes.len()]

dp[0][0] = true;

for i in 0..=s_bytes.len() {
    for j in 1..=p_bytes.len() {
        if p_bytes[j - 1] == '*' as _ {
            dp[i][j] = dp[i][j - 2] 
            || i > 0 && dp[i-1][j] && char_match!(p_bytes[j - 2], s_bytes[i - 1]);
        }
        else {
            dp[i][j] =
            i > 0 && dp[i-1][j-1] && char_match!(p_bytes[j - 1], s_bytes[i - 1]);
        }
    }
}

// ...

macro_rules! char_match {
    ($p:expr, $s:expr) => {
        ($p == '.' as _ || $p == $s)
    };
}

这是形式上最简洁的实现，但运行时间稳定在 $2$ ms，明显不如上面的自然实现，而 $O(nm)$ 的空间复杂度虽然在本题上可以忽略不计，但也有进一步优化的可能。

外分组实现

像上面一样在内循环里做模式串的字符检查： p_bytes[j-1] 是否为 * 符号的检查，以及 p_bytes[j-2] 和 p_bytes[j-2] 是否为 . 符号的检查，主要是为了代码简洁，其实不太合适，应当放到外循环里，而从实际测试看，这两者也是有可观地性能差距。

把模式串的字符检查放在外循环也就是把模式串作为主迭代，使用 $\texttt{dp}[j][i]$，在这种情况下观察 $\texttt{dp}$ 数组的使用，可以发现实际上每轮都只会使用最近三行的数据：$\texttt{dp}[j][..]$ , $\texttt{dp}[j-1][i]$ , $\texttt{dp}[j-2][i]$ ，于是我们可以只用三个数组保存数据，每次循环结束就依次交换。

pub fn solve_time_saving(s: String, p: String) -> bool {
    let p_bytes = p.as_bytes();
    let s_bytes = s.as_bytes();

    let mut pre2 = [false; MAX_S_LEN + 1];
    let mut pre1 = [false; MAX_S_LEN + 1];
    let mut cur = [false; MAX_S_LEN + 1];

    pre1[0] = true;

    for j in 1..=p_bytes.len() {
        if p_bytes[j - 1] == '*' as u8 {
            // The valid pattern has guaranteed that j >= 2
            if p_bytes[j - 2] == '.' as u8 {
                for i in 0..=s_bytes.len() {
                    cur[i] = pre2[i] || i > 0 && cur[i - 1];
                }
            }
            else {
                for i in 0..=s_bytes.len() {
                    cur[i] = pre2[i]
                        || i > 0
                            && p_bytes[j - 2] == s_bytes[i - 1]
                            && cur[i - 1]
                }
            }
        }
        else if p_bytes[j - 1] == '.' as u8 {
            cur[0] = false;

            for i in 1..=s_bytes.len() {
                cur[i] = pre1[i - 1];
            }
        }
        else {
            cur[0] = false;

            for i in 1..=s_bytes.len() {
                cur[i] = p_bytes[j - 1] == s_bytes[i - 1] && pre1[i-1];
            }
        }

        std::mem::swap(&mut pre2, &mut pre1);
        std::mem::swap(&mut pre1, &mut cur);
    }

    pre1[s_bytes.len()]
}

注意最后 pre1 代表得才是 cur 。

本实现的运行时间稳定在 $0$ ms ，堪比前面自然实现。

最省内存实现

如果仍然将文本串作为外循环的实现，$\texttt{dp}[i][j]$ 数组可以进一步压缩，因为此时只会使用三种数据： $\texttt{dp}[i-1][j-1]$ , $\texttt{dp}[i-1][j]$ , $\texttt{dp}[i][j-2]$ ，也就是本行的数据以及上一行本列和上一行前一列的数据。

因此只需要在迭代时复用一行的数据，某个位置数据在计算新的之前，保存的就是上一行的数据，可以用两个变量动态保存需要的上一行本列 $\texttt{dp}[i-1][j]$ ，和上一行前一列 $\texttt{dp}[i-1][j-1]$ 。

不过因此初始状态 $\texttt{dp}[0]$ 需要分情况处理，第一行的初始状态是 $1$ ，而其余行的初始位置是 $0$ 。

static mut DP: [bool; MAX_S_LEN + 1] = [false; MAX_S_LEN + 1];

pub fn solve_mem_saving(s: String, p: String) -> bool {
    unsafe {
        let p_bytes = p.as_bytes();
        let s_bytes = s.as_bytes();

        DP[1..].fill(false);
        DP[0] = true;

        for j in 1..=p_bytes.len() {
            if p_bytes[j - 1] == '*' as _ {
                DP[j] = DP[j - 2];
            }
        }

        // ..i

        for i in 1..=s_bytes.len() {
            let mut pre_1 = DP[0];
            DP[0] = false;

            for j in 1..=p_bytes.len() {
                let pre_0 = DP[j];

                if p_bytes[j - 1] == '*' as _ {
                    DP[j] = DP[j - 2]
                        || pre_0
                            && char_match!(p_bytes[j - 2], s_bytes[i - 1]);
                }
                else {
                    DP[j] =
                        pre_1 && char_match!(p_bytes[j - 1], s_bytes[i - 1]);
                }

                pre_1 = pre_0;
            }
        }

        DP[p_bytes.len()]
    }
}

由于本质上与基本实现一致，运行时间也是 $2$ ms 。

外分组实现2

可以参考上面通过延迟更新¹¹来节省外分组实现的一个数组的空间：

具体说就是用当前数组保存之前的数组，用上一轮的数组保存上两轮的数组，只有在当前数组更新的时候，才把当前数组保存的内容更新到上一轮数组。

static mut CUR: [bool; MAX_S_LEN + 1] = [false; MAX_S_LEN + 1];
static mut PRE1: [bool; MAX_S_LEN + 1] = [false; MAX_S_LEN + 1];


pub fn solve_time_saving(s: String, p: String) -> bool {
    unsafe {
        let p_bytes = p.as_bytes();
        let s_bytes = s.as_bytes();

        CUR[1..=s_bytes.len()].fill(false);
        CUR[0] = true;

        for j in 1..=p_bytes.len() {
            if p_bytes[j - 1] == '*' as u8 {
                // The valid pattern has guaranteed that j >= 2
                if p_bytes[j - 2] == '.' as u8 {
                    for i in 0..=s_bytes.len() {
                        let pre2 = PRE1[i];
                        PRE1[i] = CUR[i];
                        CUR[i] = pre2 || i > 0 && CUR[i - 1];
                    }
                }
                else {
                    for i in 0..=s_bytes.len() {
                        let pre2 = PRE1[i];
                        PRE1[i] = CUR[i];
                        CUR[i] = pre2
                            || i > 0
                                && p_bytes[j - 2] == s_bytes[i - 1]
                                && CUR[i - 1]
                    }
                }
            }
            else if p_bytes[j - 1] == '.' as u8 {
                PRE1[..=s_bytes.len()].copy_from_slice(&CUR[..=s_bytes.len()]);

                CUR[0] = false;

                for i in 1..=s_bytes.len() {
                    CUR[i] = PRE1[i - 1];
                }
            }
            else {
                PRE1[..=s_bytes.len()].copy_from_slice(&CUR[..=s_bytes.len()]);

                CUR[0] = false;

                for i in 1..=s_bytes.len() {
                    CUR[i] = p_bytes[j - 1] == s_bytes[i - 1] && PRE1[i-1];
                }
            }
        }

        CUR[s_bytes.len()]
    }
}

运行时间：1 ms

注解

或者用一个该题目下某用户的留言– “脑子充满了 DP” ↩
这道题有 10k 的支持，但也有 1k 的反对 ↩
只有一种可能你会做得很利落，那就是你之前根本就做过类似的，这能称得上是好的题目吗？ ↩
这就更把人引到沟里去了，因为自然解法考虑的细节就更多了 ↩
因为事先我并不熟悉这个套路，应该说套路记得我，但我不记得它 ↩
不存在可以认为是空串的情况 ↩
显然它的长度比之前保存不定串位置的数组 random_pats 少 $1$ ↩
它至少应该在上一个固定串的后面，并且保证后面有足够的空间放置其他的固定串 ↩
可以在多个测试用例里共享使用 ↩
这个开销显然很小 ↩
延迟更新、惰性更新、滚动数组，可以有很多说法儿来描述这件事儿 ↩