# 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 就是所有可能的字符数量。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/string-matching-karp-rabin.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.