---
# System prepended metadata

title: String Algorithm
tags: [2023-i2cp]

---

---
tags: 2023-i2cp

type: slide

slideOptions: 
    transition: fade;
---

<style>
.reveal .slides {
    text-align: left;
    font-size:30px;
}
</style>

# String Algorithm

Introduction to Competitive Programming

2023/04/26

----

- Trie
    - Bitwise Trie
- KMP
- Hash

---

## trie

[字典樹](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f743c2923f8170798f62a585257fdd8436cd73b6d) ( or 字首樹 )

----


![](https://miro.medium.com/max/1400/1*aJxRGNYe52CE_bVRt0E1Eg.gif =700x)

----

### 範例

[Zerojudge d518](https://zerojudge.tw/ShowProblem?problemid=d518)

給 $N$ 個字串 $s_i$, 依序讀入後輸出

前面是否有出現過此字串 $s_i$, 有出現過的話是第幾次出現的

----

### 結構

<div style="font-size: 30px">

每個節點有往下的指標
以及紀錄多少個字串以此為結尾

</div>

```cpp=
struct trie{
    trie *nxt[26];
    int cnt;    //紀錄有多少個字串以此節點結尾
    int sz;     //有多少字串的前綴包括此節點
    trie():cnt(0),sz(0){
        memset(nxt,0,sizeof(nxt));
    }
};

//創建新的字典樹
trie *root = new trie();
```

----

### 插入
將字串 $s$ 加入字典樹
```cpp=
// O(|s|)
void insert(string& s){
    trie *now = root;  // 每次從根結點出發
    for(auto i:s){
        now->sz++;
        if(now->nxt[i-'a'] == NULL){
            now->nxt[i-'a'] = new trie();
        }
        now = now->nxt[i-'a'];  //走到下一個字母
    }
    now->cnt++;
    now->sz++;
}
```

----

### 查詢

```cpp=
// O(|s|)
int query_prefix(string& s){  //查詢有多少前綴為 s
    trie *now = root;    // 每次從根結點出發
    for(auto i:s){
        if(now->nxt[i-'a'] == NULL){
            return 0;
        }
        now = now->nxt[i-'a']; 
    }
    return now->sz;
}
int query_count(string& s){  //查詢字串 s 出現次數
    trie *now = root;    // 每次從根結點出發
    for(auto i:s){
        if(now->nxt[i-'a'] == NULL){
            return 0;
        }
        now = now->nxt[i-'a'];
    }
    return now->cnt;
}
```

---

## bitwise trie

01 trie

本質也是 trie，用在跟 xor 有關的題目
看到 xor 的難題，有約 50% 是用 trie 解

將數字轉成二進位後存成 trie

----

## bitwise trie 

看題目限制換成二進位最多會有幾個位元
每個數字換成二進位從最高的位元開始儲存

![](https://i.imgur.com/4TxhN7w.png =400x)

----

### 結構
```cpp=
struct trie{
    trie *nxt[2];  // 差別
    int cnt;    //紀錄有多少個數字以此節點結尾
    int sz;     //有多少數字的前綴包括此節點
    trie():cnt(0),sz(0){
        memset(nxt,0,sizeof(nxt));
    }
};

//創建新的字典樹
trie *root = new trie();
```

----

### 插入
將數字 $x$ 加入字典樹，$O(\log x)$
```cpp=
void insert(int x){
    trie *now = root;  // 每次從根節點開始
    for(int i=30;i>=0;i--){ // 從最高位元開始往低位元走
        now->sz++;
        if(now->nxt[x>>i&1] == NULL){ //判斷當前第 i 個位元是 0 還是 1
            now->nxt[x>>i&1] = new trie();
        }
        now = now->nxt[x>>i&1];  //走到下一個位元
    }
    now->cnt++;
    now->sz++;
}
```

----

### 引入問題
一開始給 $N (N \le 10^5)$ 個數字
$Q (Q \le 10^5)$ 筆詢問，每次給你兩個數字 $v, d$
問序列中有多少個數字 xor $v$ 後 $\le d$

----

詢問多少個數字 xor $4$ 之後小於等於 $5$
![](https://i.imgur.com/BsM63sk.png =400x)

----

![](https://i.imgur.com/5MH8uAK.png)

----

![](https://i.imgur.com/yP1S1t0.png)

----

![](https://i.imgur.com/0qce1aW.png)

----

![](https://i.imgur.com/oLsr3ZF.png)

----

### 區間最大 xor 

給長度為 $N$ 的整數序列, 求出一個子區間其 xor 總和最大

- $1\le N\le 2\cdot 10^5$

----

先回到更簡單的題目, 給一個整數序列 $a$ 和整數 $d$

詢問序列中哪個數字與 $d$ xor 後最大?


此問題我們可以把先把 $a$ 中的所有數字丟進去 trie 裡面, 
再 greedy 的每次往 xor 比較大的那邊走

----

而要求出區間最大 xor, 等價於把對於每個位置當右界
找出每個位置前綴 xor 中最大的那個

使用 trie 維護所有前綴總和即可

所有之中最大的為答案

---

## Knuth–Morris–Pratt algorithm
### (KMP)

給定一個原始字串 `S`，求出單字 `W` 在字串 `S` 中所有出現的位置

$1 \le$ | `W` | $\le$ | `S` | $\le 10^6$

----

## 暴力作法

`O(|S|*|W|)`

依序窮舉 `S` 每個位置為開頭的字串，花 `O(|W|)` 時間比對字串是否相同

----

## Hash 作法

每個位置為開頭比對長度為 $|W|$ 的子字串是否相同

複雜度 $O(N)$

----

### KMP

<div style="font-size:60px">

`S` = ababcababcabd
`W` = abcabd

</div>

----

比對第一個字元相同

<div style="font-size:60px">
    
`0123456789012`
<span style="color:green">`a`</span>`babcababcabd`
<span style="color:green">`a`</span>`bcabd`
`^`

</div>

----

比對第二個字元相同

<div style="font-size:60px">
    
`0123456789012`
<span style="color:green">`ab`</span>`abcababcabd`
<span style="color:green">`ab`</span>`cabd`
&nbsp;&nbsp;`^`

</div>

----

比對第三個字元相異

<div style="font-size:60px">

`0123456789012`
<span style="color:green">`ab`</span><span style="color:red">`a`</span>`bcababcabd`
<span style="color:green">`ab`</span><span style="color:red">`c`</span>`abd`
&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

把 `W` 字串往右一格重新比對，比對失敗

<div style="font-size:60px">

`0123456789012`
`a`<span style="color:green"></span><span style="color:red">`b`</span>`abcababcabd`
&nbsp;&nbsp;<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;`^`
    
</div>

----

再把 `W` 字串往右一格重新比對，第一格相同

<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`a`</span><span style="color:red"></span>`bcababcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

比對第二格相同
<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`ab`</span><span style="color:red"></span>`cababcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`ab`</span><span style="color:red"></span>`cabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

比對第三格相同
<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`abc`</span><span style="color:red"></span>`ababcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abc`</span><span style="color:red"></span>`abd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

比對第四格相同
<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`abca`</span><span style="color:red"></span>`babcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abca`</span><span style="color:red"></span>`bd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

比對第五格相同
<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`abcab`</span><span style="color:red"></span>`abcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abcab`</span><span style="color:red"></span>`d`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

----

比對第六格相異
<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`abcab`</span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abcab`</span><span style="color:red">`d`</span>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

----

再把 `W` 字串往右一格重新比對，第一格相異

<div style="font-size:60px">

`0123456789012`
`aba`<span style="color:green"></span><span style="color:red">`b`</span>`cababcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

再把 `W` 字串往右一格重新比對，第一格相異

<div style="font-size:60px">

`0123456789012`
`abab`<span style="color:green"></span><span style="color:red">`c`</span>`ababcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

----

再把 `W` 字串往右一格重新比對，第一格相同

<div style="font-size:60px">

`0123456789012`
`ababc`<span style="color:green">`a`</span><span style="color:red"></span>`babcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">a</span><span style="color:red"></span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第二格相同

<div style="font-size:60px">

`0123456789012`
`ababc`<span style="color:green">`ab`</span><span style="color:red"></span>`abcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">ab</span><span style="color:red"></span>`cabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第三格相異

<div style="font-size:60px">

`0123456789012`
`ababc`<span style="color:green">`ab`</span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">ab</span><span style="color:red">`c`</span>`abd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

再把 `W` 字串往右一格重新比對，第一格相異

<div style="font-size:60px">

`0123456789012`
`ababca`<span style="color:green"></span><span style="color:red">`b`</span>`abcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

再把 `W` 字串往右一格重新比對，第一格相同

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">a</span><span style="color:red"></span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第二格相同

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">ab</span><span style="color:red"></span>`cabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`ab`</span><span style="color:red"></span>`cabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第三格相同

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">`abc`</span><span style="color:red"></span>`abd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abc`</span><span style="color:red"></span>`abd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第四格相同

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">`abca`</span><span style="color:red"></span>`bd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abca`</span><span style="color:red"></span>`bd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第五格相同

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">`abcab`</span><span style="color:red"></span>`d`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abcab`</span><span style="color:red"></span>`d`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

第六格相同，找到一組解

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">`abcabd`</span><span style="color:red"></span>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abcabd`</span><span style="color:red"></span>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

----

會發現過程中，有很多不必要的匹配

----

<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`abcab`</span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`abcab`</span><span style="color:red">`d`</span>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

----


<div style="font-size:60px">

`0123456789012`
aba<span style="color:green"></span><span style="color:red">`b`</span>`cababcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`
    
</div>

每次失敗就要重頭開始嘗試匹配

----

在匹配失敗時，前面已經有一段不用重新匹配
我們只需要從那之後開始匹配即可

<div style="font-size:60px">

`0123456789012`
`ab`<span style="color:green">`abc`<u>`ab`</u></span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green"><u>`ab`</u>`cab`</span><span style="color:red">`d`</span>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

----

從第3個字元開始匹配

<div style="font-size:60px">

`0123456789012`
`ababc`<span style="color:green">`ab`</span><span style="color:red">`a`</span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`ab`</span><span style="color:red">`c`</span>`abd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

再次匹配失敗，把字串移動到必要的匹配上

----

從第1個字元開始匹配

<div style="font-size:60px">

`0123456789012`
`ababcab`<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green">`a`</span><span style="color:red"></span>`bcabd`
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`^`

</div>

----

## 次長相同前綴後綴

可以知道最長相同前綴後綴是字串自己本身

而我們要求的是次長，以 `abcabd` 為例

| 字串 | 次長相同前綴後綴 |
| --- | ------------- |
|`a`      | $\phi$
|`ab`     | $\phi$
|`abc`    | $\phi$
|<u>`a`</u>`bc`<u>`a`</u>   | `a`
|<u>`ab`</u>`c`<u>`ab`</u>  | `ab`
|`abcabd` | $\phi$

----

## failure function

則當匹配失敗時，取其次長相同前綴後綴，
則可以直接移動詢問字串 `W` 到還未匹配過的位置

```python
while 還沒比對到最後一個字元:
    if 比對字元成功:
        比對下一個字元
    else if 比對字元失敗:
        取其次長相同前綴後綴，移動字串 W
    else if 成功匹配整個字串:
        紀錄答案，並且取其次長相同前綴後綴，移動字串 W
```

----

為了實作方便，
會將儲存次長相同前綴後綴最後一個字元的 index (0-base)

| 字串 | 次長相同前綴後綴index |
| --- | ------------- |
|`a`      | $-1$
|`ab`     | $-1$
|`abc`    | $-1$
|<u>`a`</u>`bc`<u>`a`</u>   | $0$
|<u>`ab`</u>`c`<u>`ab`</u>  | $1$
|`abcabd` | $-1$

如果為空字串則為 `-1`，第一個 index 為 `0`，所以設前一個 `0-1 = -1`

----

## 程式碼

```cpp=
int failure[MXN];  //儲存以第i個為結尾的次長相同前綴後綴
void KMP(string s, string w){
    // i 為字串 s 當前 index, j 為字串 w 以匹配到的 index
    for(int i = 0,j = -1; i < s.size(); ++i){
        while(j >= 0 && s[i] != w[j+1]){ // 當匹配失敗找到次長相同前綴後綴，移動字串W
            j = failure[j];
        }
        if(s[i] == w[j+1]){ // 當字元相等
            ++j;
        }
        if(j+1 == w.size()){ //  當字串完全匹配
            ans.push_back(i-w.size()+1); // 加進答案
            j = failure[j]; // 移動字串W
}}}
```

----

## build

建 次長相同前綴後綴表

當一個字串想要加長 次長相同前綴後綴
則需在最尾端加上一個跟前綴下一個字元相同的字元
如果下一個相同代表可以加長，否則需要回到當前的次長相同前綴後綴

<u>ab</u>cc<u>ab</u> $\to$ <u>ab<span style="color:red">c</span></u>c<u>ab<span style="color:red">c</span></u>

----

因此當我們求出前 $i$ 個字元的次長相同前綴後綴，
如果想要求 $i+1$ 的次長相同前綴後綴

則是看原本的位置指到字元能不能加長

如果相同則可以加長
否則則找次長相同前綴後綴

----

## 程式碼

```cpp=
int failure[MXN];
void build_failure(string& w){
    for(int i=1,j=fauilre[0]=-1;i<w.size();i++){
        while(j>=0 && w[i] != w[j+1]){ //當不相同無法匹配
            j = failure[j];
        }
        if(w[i] == w[j+1]){ // 如果可以加長長度，則為前一個答案+1
            ++j;
        }
        failure[i] = j; // 紀錄答案
    }
}
```

----

## 複雜度

### build failure table

字元兩兩比對次數最多 $2 |W|$ 次

比對成功，長度增長；比對失敗，長度減短。總共增長 $|W|$ 次、最多減短 $|W|$ 次。邊框長度最多變動 $2 |W|$ 次

### search word

字元兩兩比對次數最多 2|S| 次
原理同上

複雜度 $O(|W|+|S|)$

---

## hash

中文叫雜湊

雜湊函式(hash function) 把資料壓縮，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值。雜湊值通常用一個短的隨機字母和數字組成的字串來代表

----

### rolling hash

選一個整數 $p$ , 把字串轉換成 $p$ 進位的數字來儲存

原本字串比對是否相同需要 $O(|S|)$, 轉換成數字比較是否相同只需要 $O(1)$ 的時間

----

S = "ABCA" 為例, 轉成 $p$ 進位 
則會變成 $A\cdot p^3 + B\cdot p^2 + C\cdot p^1 + A \cdot p^0$

而當字串非常長的時, 轉換會超出 long long 範圍
因此通常會進行 mod 後再儲存

----

$p$ 通常大於值域的質數降低碰撞機率 ( ex:  13331, 14341, 75577)

mod 為模數，通常選質數降低碰撞機率，選約為 $10^9$ 附近的數字避免計算過程溢位
    (ex: $10^9$+7, 998244353, 999997771)

可以把一些質數放[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/primes.cpp)以被不時之需

----

### 建表

$H_{0,k}$ 為字串 $s[0,k]$ hash 出來的結果

$H_{0,k} = (s_0\cdot p^k + s_1\cdot p^{k-1} + s_2\cdot p^{k-2} ... + s_k\cdot p^0)$ % mod
$\to H_{0,0} = (s_0\cdot p^0)$ % mod
$\to H_{0,1} = (H_{0,0}\cdot p + s_1)$ % mod
$\to H_{0,2} = (H_{0,1}\cdot p + s_2)$ % mod
$\to H_{0,i} = (H_{0,i-1}\cdot p + s_i)$ % mod

----

建立所有前綴的 Hash 值 $H_{[0:k]}$

```cpp=
const ll P = 75577;
const ll MOD = 998244353;
ll Hash[MXN];    //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
    int val = 0;
    for(int i=0; i<s.size(); i++){
        val = (val * P + s[i]) % MOD;
        Hash[i] = val;
    }
}
```

----

### 字串子區間的 Hash 值

$Q$ 筆詢問，每次問字串 $s$ 中有沒有某個子字串為 $x$

假設要求字串 $s$ 區間 $[l,r]$ 的Hash值為


$H_{l,r} = (s_l * p^{r-l+1} + s_{l+1} * p^{r-l} + s_{l+2} * p^1 + ... +s_r * p^0)$ % mod

$\to (H_r - H_{l-1} * p^{r-l+1})$

----

以區間[1,3]為例

<div style="font-size: 30px">

$H_{0,3} = (s_0 * p^3 + s_1 * p^2 + s_2 * p^1 + s_3 * p^0)$ % mod

$H_{0,0} = (s_0 * p^0)$ % mod

$H_{0,3} - H_{0,0} * p^3$

$=(s_0 * p^3 + s_1 * p^2 + s_2 * p^1 + s_3 * p^0)-(s_0 * p^3)$ % mod

$=(s_1 * p^2 + s_2 * p^1 + s_3 * p^0)$ % mod

$=H_{1,3}$

</div>

----

前面 $O(N)$ 建好前綴 Hash 表
即可 $O(1)$ 時間計算所有子字串的 Hash 值

而如果題目需要不斷詢問 字串中兩個不同的子區間是否為相同字串時，即可 $O(1)$ 判斷

----

## double hashing

在某些題目測資特別設計之下, 可能發生碰撞

在這種情況下，我們會再多選一個 $p_2$ 或者 $mod_2$ 重新建立新的 Hash 值
使得每個區間都有兩個 Hash 值

----

```cpp=
const ll P1 = 75577;
const ll P2 = 12721;    // 多一個質數 p2
const ll MOD = 998244353;
pair<ll,ll> Hash[MXN];    //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
    pair<ll,ll> val = make_pair(0,0);
    for(int i=0; i<s.size(); i++){
        val.first = (val.first * P1 + s[i]) % MOD;
        val.second = (val.second * P2 + s[i]) % MOD;
        Hash[i] = val;
    }
}
```

----

## Longest Palindromic Substring

給定一個字串 $s (1 \le |s| \le 10^5)$，求所有的回文子字串中，長度最長為多少

"ababa" $\to$ 5
"caaabc" $\to$ 3

----

## brute force

暴力窮舉所有區間 $O(N^2)$
再花 $O(N)$ 時間檢查窮舉的區間是否為回文
複雜度 $O(N^3)$

----

## brute force with hash

hash 後可以花 O(1) 時間知道字串某個子區間的hash值

如果一個字串是回文，則字串本身與反過來會相同

先預處理
字串 $s$ 的 hash 值以及
反轉的字串 reverse($s$) 的 hash 值

則可以花 $O(1)$ 時間判斷字串是否為回文

複雜度 $O(N^3) \to O(N^2)$

----

但還可以更快

如果一個字串是回文，
把最左以及最右的字元刪掉也是回文
或者最左最右分別加上相同字元也是回文

s="abaaba"

同時刪除最左右 $\to$ "baab"
同時加上字元'c' $\to$ "cabaabac"

----

因此具有單調性可以使用二分搜!

二分搜尋最長回文半徑 $r$，
每次判斷以每個字元為中心且半徑為 $r$ 的字串是否為回文

如果是回文，則代表此字串最長回文半徑至少為 $r$
不是回文則代表此字串最長回文半徑小於 $r$

檢查是否為回文可以用 hash $O(1)$ 判斷

----

而回文也分為兩種，長度為奇數或偶數

若為奇數，中心點為字元 "abcba"
若為偶數，中心點為空白 "abba"

所以檢查時兩種情況(中心為字元或空白)都要檢查

----

## 複雜度

對於每個位置當成中心點, 二分搜最長回文長度
每個字元或空白為中心且半徑為 $r$ 的字串是否為回文

總共 $O(N)$ 個位置 二分搜 $O(\log N)$

複雜度 $O(N\log N)$

----

有些字串的題目都具有單調性使之可以二分搜尋

再搭配 hash，通常都可以做到 $O(N\log N)$ 的複雜度

----

## [Hash + 修改](https://cses.fi/problemset/task/2420)

給定一個字串, 兩種操作

1. 詢問區間 [l, r] 是否為回文
2. 修改第 $i$ 個字元

多了第二種操作 修改字元

----

可以發現我們 Hash[i] 儲存的是前綴 Hash 值
修改第 $i$ 個字元會影響到 Hash[i:n]


也就是從第 $i$ 個位置的 Hash 值到最後一個的 Hash 值

----

而原本 hash 的建法

Hash[2] = $p^2\cdot s[0] + p^1\cdot s[1] + p^0\cdot s[2]$
Hash[3] = $p^3\cdot s[0] + p^2\cdot s[1] + p^1\cdot s[2] + p^0\cdot s[3]$

會發現修改位置 2 則, 後面每格的 hash 值對於 s[2] 乘的 $p$ 冪次會不同

----

因此我們通常會把 $p$ 的冪次反過來建表

Hash[2] = $p^0\cdot s[0] + p^1\cdot s[1] + p^2\cdot s[2]$
Hash[3] = $p^0\cdot s[0] + p^1\cdot s[1] + p^2\cdot s[2] + p^3\cdot s[3]$

如此一來修改某個元素時, 對於所有 Hash[$i:n$] s[i] 乘上的冪次都會相同不影響

----

區間修改從 $i$ 開始到結尾的
因此我們可以使用 BIT 等資料結構來維護區間加值

使用 BIT 記得要 1-base, 可以在字串前面加上一個填充字元

----

從修改的位置 pos 加值, 加的值 為新字元與舊字元的差值 $\times p$ 的 pos 次方
所有 $p$ 的次方可以在一開始先 $O(N)$ 預處理

由於要求回文, 因此要儲存正反字串分別的 Hash 值

```cpp
void update(int pos, int ch){
    BIT.update(pos, (ch - s[pos]) * p[pos] % MOD);
    revBIT.update(n-1-pos, (ch-s[pos]) * p[n-pos-1] % MOD);
}
```

----

### 總複雜度

修改 $O(\log N)$
詢問 $O(1)$

---

### 2023 海洋盃

![](https://i.imgur.com/zHbeklQ.png)

熱身賽算一次加分
正式賽算一次模擬賽成績

報名連結： https://forms.gle/UEVqGczed4VPjach9
粉絲專頁： https://www.facebook.com/OceanCupProgrammingContest

----

### Homework and Practice

deadline: 5/6
link: https://vjudge.net/contest/555030