String Algorithm

Introduction to Competitive Programming

2023/04/26

trie

字典樹 ( or 字首樹 )

bitwise trie

01 trie

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

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

字串	次長相同前綴後綴
`a`	\(\phi\)
`ab`	\(\phi\)
`abc`	\(\phi\)
`abca`	`a`
`abcab`	`ab`
`abcabd`	\(\phi\)

字串	次長相同前綴後綴index
`a`	\(-1\)
`ab`	\(-1\)
`abc`	\(-1\)
`abca`	\(0\)
`abcab`	\(1\)
`abcabd`	\(-1\)

1 . 1

String Algorithm Introduction to Competitive Programming 2023/04/26

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

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

	// 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++;
	}

	// 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;
	}

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

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

	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++;
	}

String Algorithm

trie

範例

結構

插入

查詢

bitwise trie

bitwise trie

結構

插入

引入問題

區間最大 xor

Knuth–Morris–Pratt algorithm

(KMP)

暴力作法

Hash 作法

KMP

次長相同前綴後綴

failure function

程式碼

build

程式碼

複雜度

build failure table

search word

hash

rolling hash

建表

字串子區間的 Hash 值

double hashing

Longest Palindromic Substring

brute force

brute force with hash

複雜度

Hash + 修改

總複雜度

2023 海洋盃

Homework and Practice

	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
	}}}

	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; // 紀錄答案
	}
	}

	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;
	}
	}

	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;
	}
	}