Tire 字典樹

\[Tire

\]

【雜言】：

本來因為\(KMP\)沒有打完，是以還沒有打算進行\(Tire\)字典樹的學習，既然\(gyh\)學長講了，那就自然整理一下了。也正是因為今天，我開放了所有的學習筆記。

【前置芝士】：

基礎圖論 ， 隻需要明白建樹即可。無需其他的太多的東西，反正我是這麼認為的。，有效狀态自動機

【算法流程】：

\(Tire\)字典樹可以用來解決"一個字元串是否出現過"，并以這個問題來簡要的概述一下流程。

輸入\(3\)個字元串， \("Zmon" , "Zmck" "les"\) , 這\(3\)個 ， 查詢一下"Zmon"和"Zmaa"是否存在。

我們首先建一顆樹 ， 節點是一個虛點\(now\)，然後加入：

1. 加入\(Zmon\), 就是\(now \to Z \to m \to o \to n\) 建一條樹邊
2. 加入\(Zmck\),發現在建立\(Z,m\)時，早就有已經建立過的樹邊了，那麼這時候，我們也隻需要在\(m\)的後面建樹邊也就是\(m \to c \to k\) ,
3. 加入\(llon\) ,發現\(l\)節點沒有建立，那麼我們建一個\(l\)這個節點，連接配接虛點，進而形成一條樹邊，也就是$now \to l \to e \to s $ 這一條樹邊 。 描述的很清楚了，建完之後就是下面這一幅圖，比較難看，将就一下。

下面就是\(Zmon\)的查詢了，我們可以看到，查詢是字元進行比較， 比較第一個字元是有的，也就是\(Z\) , 我們發現有兩條樹邊由\(Z\)作為起始點，并且下一個節點是\(m\)， 那麼我們比對的時候，繼續從\(m\)進行比對，看一下\(m\)連接配接的節點，有一個\(o\)，那麼,沿着樹邊繼續尋找，找到了\(n\)并且下面沒有節點，那麼比對（其實意思也就是從now的下一個節點一直到葉子節點就是一個單詞）

關于\(Zmaa\) 的查詢,我們運用上帝視角發現，其實沒有，我們還是模拟一下計算機吧，一直到\(m\)就不再贅述了，和上段一緻 ， 同時 ，到了\(a\)這個字元比對，發現這個節點中是沒有這個的，那麼我們就直接\(return \ \ false\),就\(OK\)了，證明這一個點不存在

[【例題】] (https://www.luogu.com.cn/problem/P2580)：

題目就不贅述了，直接上代碼，如是不會，詳解其題解。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#define int long long 
const int kmaxn = 2e6 ;
const int kbase = 13331 ;
const int kmod  = 1e7 + 1;
using namespace std ; 
inline int read()
{
	int x = 0 , f = 1 ; char ch = getchar() ;
	while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
	while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
	return x * f ;
}
struct Tire
{
	int ch[kmaxn][27] , now ,val[kmaxn] ; 
	//ch是第幾個單詞出現的次數 
	Tire()
	{
		now = 1 ; //建立虛點 
		memset(ch[0] , 0 , sizeof(ch[0])) ;
		memset(val , 0 , sizeof(val)) ;
	}
	void insert(char *s) //插入一個單詞
	{
		int p = 0 ; 
		int lth = strlen(s+1) ;
		for(int i = 1 ; i <= lth ; i++)
		{
			if(!ch[p][s[i] - 'a']) //如果這一個節點不存在，那就建立節點
			{
				memset(ch[now] , 0 , sizeof(ch[now])) ;
				ch[p][s[i] - 'a'] = now++ ;				
			}  
			p = ch[p][s[i]-'a'] ;//繼續向下尋找 
		}
	} 
	int query(char *s)
	{
		int p = 0 , lth = strlen(s+1) ;
		for(int i = 1 ; i <= lth ; i++)
		{
			if(!ch[p][s[i] - 'a']) return 0 ;
			p = ch[p][s[i]-'a'] ;
		}
		if(!val[p]) 
		{
			val[p] = 1 ; return 1 ;
		}
		return 2 ; 
	}
}tire;
char s[kmaxn] ;
int m , n ;
signed main()
{
	n = read() ;
	for(int i = 1 ; i<= n ;i++)
	{
		scanf("%s" ,s+1) ;
		tire.insert(s) ;
	}
	m = read() ;
	while(m--)
	{
		scanf("%s" , s+1) ;
		int opt = tire.query(s) ;
		if(opt == 0) printf("WRONG\n") ;
		if(opt == 1) printf("OK\n") ;
		if(opt == 2) printf("REPEAT\n") ;
	}
	return 0 ;
}