# String Matching, Karp-Rabin

## String Matching Problem

> 给定两个字符串 s 和 t，判断 s 是否是 t 的子串？如果是，出现在哪？出现了多少次？

## Naive/Brute Force Algorithm

```python
def match(s, t):
    return any(s == t[i:i+len(s)] for i in range(len(t)-len(s))
```

子串比较的复杂度：$$O(|s|)$$ ，因此算法时间复杂度为 $$O(|s|*(|t|-|s|))$$ ，近似为 $$O(|s|*|t|)$$ 

## Karp-Rabin Algorithm

### Rolling Hash ADT

在 Naive Algorithm 中，我们每次比较子串的复杂度都是 $$O(|s|)$$ ，但实际上，前后两次比较中，即 $$s == t\[i:i+len(s)]$$ 与 $$s == t\[i+1:i+len(s)+1]$$ ，两个 t 的子串有 $$len(s)-1$$ 个字母是重复的，如果能够不用重复比较这些比较过的字母，就有可能将比较子串的复杂度将到 $$O(1)$$ 。

于是 Rolling Hash ADT 诞生了：它维护一个字符串 x，同时提供以下三个方法

| 方法          | 功能                                     |
| ----------- | -------------------------------------- |
| r()         | r 就是 hash function，r() 返回当前子串的哈希值 h(x) |
| r.append(c) | 将字母 c 放到 x 的末尾                         |
| r.skip(c)   | 将 x 的第一个字母移除                           |

### Karp-Rabin

```python
def karp_r(s, t):
    for c in s:
        rs.append(c)
    for c in t[:len(s)]:
        rt.append(c)
    if rs() == rt():
        # compare char by char
        pass
    
    for i in range(len(s), len(t)):
        rt.skip(t[i-len(s)])
        rt.append(t[i])
        if rs() == rt():
            # compare char by char
            pass
```

分析：

如果 Rolling Hash ADT 能够做到：

> 两个不同的子串的哈希值相等的概率 < $$\frac{1}{|s|}$$&#x20;

Karp-Rabin Algorithm 的算法复杂度就是：

$$
O(|s| + |t|*|s|*\frac{1}{|s|}) = O(|s| + |t|)
$$

#### An Rolling Hash Data Structure

想象 string x 是一个基数（base）为 a 的多位数（multi-digit number）u ：

| 方法          | 基本实现                                             | 优化实现                                                                                                                       |       |                                         |   |                                                                                      |   |                                   |
| ----------- | ------------------------------------------------ | -------------------------------------------------------------------------------------------------------------------------- | ----- | --------------------------------------- | - | ------------------------------------------------------------------------------------ | - | --------------------------------- |
| r()         | $$u \bmod p$$ ，其中 p 是接近 \|s\| 的随机质数，r 中保存着 u 和 x | $$u \bmod p$$ ，其中 p 是接近 \|s\| 的随机质数， r 中保存着 $$u \bmod p$$ 和 $$                                                             | x     | $$ ，而并非 u                               |   |                                                                                      |   |                                   |
| r.append(c) | $$u = u·a + ord(c)$$                             | <p><span class="math">(u · a + ord(c))\bmod p</span> 即<br><span class="math">\[(u \bmod p)·a + ord(c)] \bmod p</span> </p> |       |                                         |   |                                                                                      |   |                                   |
| r.skip(c)   | $$u = u - c·a^{                                  | x                                                                                                                          | -1}$$ | <p><span class="math">\[u - ord(c)·(a^{ | x | -1} \bmod p)] \bmod p</span>  即</p><p><span class="math">\[(u \bmod p) - ord(c)·(a^{ | x | -1} \bmod p)] \bmod p</span> </p> |

在实际问题中 a 就是所有可能的字符数量。