本文作者潘愷璠參加過清北學堂NOIP2017訓練營提高組精英班，筆記非常詳細。特分享給大家！基本數論相關筆記較多，為方便大家閱讀，我們預計會分為三到四篇文章介紹給大家。

基本數論（三）一、Trie樹：1.定義：通過字元串建成一棵樹，這棵樹的節點個數一定是最少的。例如：4個字元串"ab","abc","bd","dda"對應的trie樹如下：

其中紅色節點表示存在一個字元串是以這個點結尾的。一個性質：在樹上，兩個點u,v滿足u是v的祖先，那麼u代表的字元串一定是v代表的字元串的前綴。2.Trie樹的插入：可以從根節點出發，每次沿著要走的字元串往下走，若沒有則建立新節點。假如所有字元串的長度之和為n，構建這棵trie樹的時間複雜度為O(n)。int root=1;int cnt=1;int p[i][j];//表示從i這個節點沿著j這個字元走，能走到哪個點，走不到就是0char s[];//存儲字元串for(int i=1;i<=n;i++)

{

scanf("%s",s);int len=strlen(s);int now=root;//now表示走到的當前節點，now的初始值為根節點for(int j=0;j<len;j++){if(p[now][s[j]]>0){now=p[now][s[j]];//如果能沿著j節點往下走，直接往下走}else{

pow[now][s[j]]=++cnt;

now=p[now][s[j]];}}v[now]++;//記錄now這個節點被訪問的次數}3.Trie樹的查詢：可以看出trie樹中每個節點表示其中一個字元串的前綴，在做題過程中往往通過這個性質來得到較好的時間複雜度。4.一個例題：給定n個互不相同的串，求存在多少對數(i,j)（共n2對）滿足第i個串是第j個串的前綴。所有串的長度之和≤500000。解題：根據性質，「在樹上，兩個點u,v滿足u是v的祖先，那麼u代表的字元串一定是v代表的字元串的前綴」。

我們要滿足一個串是另一個串的前綴，也就是說，在trie樹上，這個串對應的位置是另一個串對應的位置的祖先。

構建這棵trie樹，然後我們枚舉每個紅色點，它對答案的貢獻是以它為根的子樹中紅色節點的個數之和。這個東西可以在一開始遍歷這棵樹預處理出來！時間複雜度是線性的。void dfs(int x){if(v[x]) sum[x]++;for(char i=a;i<=z;i++){if(p[x][i])//從當前x沿著i這個字元走還能往下走{

dfs(p[x][i]);//往下走

sum[x]+=sum[p[x][i]];//累加貢獻sum}}}dfs(1);//從根節點開始5.USACO的某題（這題真的亂）：給定n個串，重排字元之間的大小關係，問哪些串有可能成為字典序最小的串。所有字元串的長度之和<=100000。例如，有一個字元串，裡面只有a~z這些字元，默認地，a是最小的，z是最大的。但是我們可以重新定義字元間的大小關係，比如這樣：b<c<d<y<x<z，從而我們對於一些字元串，就按照我們新定義的大小關係來比較字典序大小。舉個栗子：

三個字元串"aab","aba","baa"，總共只出現了兩個字元a和b，所以字元間的大小關係要麼是a<b要麼是a>b，假設a<b，則第一個串"aab"就是字典序最小的串；假設b<a，則第三個串"baa"就是字典序最小的串，但是對於第二個串，無論我們怎麼定義字元間的大小關係，都不可能成為三個字元串中字典序最小的。

解題：首先對這n個串構建trie樹，之後對每個串，從根走向它，這個路程中遇到的所有兄弟在字典序下都比它大。對於每個串，從前往後，直接確定這個字元的大小關係，判斷是否是字典序最小。以下兩個串都是有可能成為字典序最小的串的：abcd…xyzaabcd…xyzb所以有：u是v的前綴，則v一定不是字典序最小的串。現在問題來了：對於每個串，在什麼條件下，是字典序最小的？？來個栗子：有一些字元串（"aabc"，"aac"，"aad"，"ac"，"adb"，"aabb"），構造trie樹如下：

對於"aabc"這個串，往下遍歷：從深度為2的那一層，我們可以得到：a<c,a<d；從深度為3的那一層，我們可以得到：b<c,b<d；從深度為4的那一層，我們還可以得到：c<b。綜上所述：我們得到了一堆的關係：a<c,a<d；b<c,b<d；c<b，容易看出，這些關係是存在矛盾的，所以無解->"aabc"是不可能成為字典序最小的串。所以要想有解，這一堆的關係必須滿足兩個條件：①不存在矛盾②不存在環總的來說，就是判斷這一堆的關係是否存在拓撲序！最多有26×26個大小關係，而最多有100000個字元串，所以時間複雜度最大為：O(26×26×100000)。二、KMP演算法（「看mao片演算法」~咳咳）：

給定兩個字元串A,B，判斷T是否為S的子串（變式：尋找子串B在串A中的位置）。

要求一個O(|A|+|B|)的做法。通常稱A為目標串（或主串），B為模式串。演算法過程：我們假設串A的長度為n，串B的長度為m，每個字元串的開頭下標默認為1。

定義兩個變數i和j，這兩個變數共同表示：A[i-j+1~i]與B[1~j]均匹配，即：A中以第i個字元結尾的、長度為j的字元串，和B從頭開始長度為j的字元串完全匹配。

繼續往下匹配：如果i+1和j+1不匹配。

現在，就是用到了KMP演算法的核心：它對這一情況的處理方式是減少j，就相當於將子串向右平移。平移的目的是為了讓「A[i-j+1~i]與B[1~j]均匹配」這個條件重新滿足。

在上圖中，j一直減小到了0，因為向右平移的過程中，始終不能讓這個條件滿足（最右邊"?"部分已經越界）但有時候，將j減少一點點之後，是可以重新滿足條件的，例如：

那麼我們將j從7減小到4時，有：

這樣就可以完全匹配啦！但是後面還有沒有匹配的機會我們就不管了，至少我們已經保證A[4~7]和B[1~4]完全匹配上了。現在考慮一個問題：我們每次把j減小1（一位一位地平移B字元串），這樣太慢了，我們在這裡預處理一個next[]數組，表示當j匹配不下去的時候，我們可以把j減少到next[j]，繼續嘗試匹配。預處理過程：讓j自己和自己匹配一下，一旦匹配發現B[k-m+1~k] 和 B[1~m] 匹配，則說明在A與B匹配過程中，j等於k匹配不下去時，j可以嘗試減小到m。過程如下：

/**************************************///靚麗的分界線

一些代碼：/*核心內容*/for(int i=1,j=0;i<=n;i++){while(j&&B[j+1]!= A[i]) j=next[j];if(B[j+1]==A[i]) j++;if(j==m){printf("%d
", i-j+1);//輸出找到的"B字串在 A中位置"//如果要求的是出現次數，這裡也有可能是ans++什麼的j=next[j];//讓循環進行下去}}for(int i=2,j=0;i<=m;i++)/*預處理next[]數組*/{while(j&&B[j+1]!=B[i]) j=next[j];if(B[j+1]==B[i]) j++;next[i]=j;}經典例題：Blue jeans（POJ 3080）給定m個串，求字典序最小的公共子串。找一個串，使得這個串是所有串的子串，並且字典序最小。m≤10，每個串的長度≤60.解題思路：一個串，如果是所有串的子串，那麼肯定是第一個串的子串。枚舉所有子串，複雜度為60*60。驗證其它串是否包含這個子串，複雜度為10*60。每次更新答案即可。時間複雜度為：O(603×10)經典例題：Seek the Name,Seek the Fame（POJ 2752）給定一個字元串S，求所有既是S的前綴又是S的後綴的子串，從小到大輸出這些串的長度。|S|<=500000。N為字元串S的長度。解題思路：回到KMP演算法，我們令P[j]表示找最大的數x，使得B中位置是1~x的字元與j-x+1~j的字元完全相同，也就是上面講的KMP演算法中的next[]。考慮P[|S|]的意義，也就是最大的前綴等於後綴的長度（不包括其本身）。那P[P[|S|]]就是次大的。因此所有P[P[…P[|S|]]]就是答案了，一直這樣遞歸下去就可以找到答案。或者用Hash來做，這樣更容易想到也比較方便，但效率沒有KMP高。
推薦閱讀：
相关文章