---
tags: 字串
title: KMP, Z-Value
---

:::info
## 題目：
- [TIOJ 1306 模板題](https://tioj.ck.tp.edu.tw/problems/1306)
給定字串 $S, T$ ，求 $S$ 在 $T$ 裡出現幾次

aba
abababa
-> 3

aaa
aaaacaaa
-> 3

aaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaab
->0
- [TIOJ 1091 挑戰題](https://tioj.ck.tp.edu.tw/problems/1091)
- [HDOJ 6629](http://acm.hdu.edu.cn/showproblem.php?pid=6629)
:::

### 兩層for loop：
- 複雜度：$O(|S|\times|T|)$

:::success
## KMP
- failure-function -> f 定義：
- $f(i)$ 是第i個index前面次長匹配前綴後綴的點
- 舉個例子：
- $S$ = "dadacdad"，index 從 0 開始

| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| -1 | -1 | 0 | 1 | -1 | 0 | 1 | 2 |

- 求法：
- $S$ = "dadacdad"，index 從 0 開始

    fail[100000];
    void calc_fail(string S){
        fail[0] = -1;
        int cur = -1;
        for(int i = 1; i < S.size(); ++i){
            while(cur != -1 && s[i] != s[cur+1]){
                cur = fail[cur];
            }
            if (S[cur+1] == S[i]) cur++;
            fail[i] = cur;
        }
    }

- 用法：
- $S$ = "aba"
- $T$ = "abbabaababa"

    fail[100000];
    int calc_times(string S, string T){
        int ret = 0;
        int cur = -1;
        for(int i = 1; i < T.size(); ++i){
            while(cur != -1 && T[i] != S[cur+1]){
                cur = fail[cur];
            }
            if (S[cur+1] == T[i]) cur++;
            if (cur == S.size()-1) ret++;
        }
        return ret;
    }

- 複雜度：$O(|S|+|T|)$
:::

:::success
## Z-Value
- Z-function -> f 定義：
- $f(i)$ 是第i個index往後的字串跟原字串的最長共同前綴長度
- 舉個例子：
- $S$ = "dadacdad"，index 從 0 開始

| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 0 | 0 | 2 | 0 | 0 | 3 | 2 | 1 |

- 計算 Z-function：

    int z[100000];
    void calc_Z(string S){
        int cur = 0;
        z[0] = 0;
        for(int i = 1; i < S.size(); ++i){
            if(z[cur] + cur < i)z[i] = 0;
            else z[i] = min(z[cur] + cur - i, z[i-cur]);
            while(i+z[i] < S.size() && S[z[i]] == S[i+z[i]])++z[i];
            if(z[i] + i > z[cur] + cur)cur = i;
        }
    }

- 用法

    int z[100000];
    int calc_times(string S, string T){
        int ret = 0;
        int rec = S.size();//原本s長度
        S += T;//串起來w
        int cur = 0;
        z[0] = 0;
        for(int i = 1; i < S.size(); ++i){
            if(z[cur] + cur < i)z[i] = 0;
            else z[i] = min(z[cur] + cur - i, z[i-cur]);
            while(i+z[i] < S.size() && S[z[i]] == S[i+z[i]])++z[i];
            if(z[i] + i > z[cur] + cur)cur = i;
            if(i >= rec && z[i] >= rec)++ret;
        }
        return ret;
    }

- 複雜度：$O(|S|+|T|)$
:::

:::success
## 要停電了.....各位...

### 下禮拜課表 (有人能跟我解釋螢光筆的意思嗎?)

#### 黃色標記部分為線上同步補課，其餘為自主學習 by官網

<iframe src="https://onedrive.live.com/embed?cid=1AC05B16CD43760F&resid=1AC05B16CD43760F%213538&authkey=AGozp8-N7Z1friI&em=2" width="700" height=900" frameborder="0" scrolling="no"></iframe>

### 我好可愛~~
### 看我嘛 ~ 看我嘛 ~ 看我嘛 ~ 喵 ~
### 要戴口罩歐 喵~
### 早安 喵～
### 我也要吃泡麵拉 喵~

<iframe width="700" height="400" src="https://onedrive.live.com/embed?cid=1AC05B16CD43760F&resid=1AC05B16CD43760F%213537&authkey=AGLIcFfJMQxdToY" ;frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
:::