|
一、Trie樹
1.定義： 通過字符串建成一棵樹，這棵樹的節(jié)點(diǎn)個(gè)數(shù)一定是最少的。例如：4個(gè)字符串'ab','abc','bd','dda'對應(yīng)的trie樹如下： 其中紅色節(jié)點(diǎn)表示存在一個(gè)字符串是以這個(gè)點(diǎn)結(jié)尾的。 一個(gè)性質(zhì)：在樹上，兩個(gè)點(diǎn)u,v滿足u是v的祖先，那么u代表的字符串一定是v代表的字符串的前綴。
2.Trie樹的插入： 可以從根節(jié)點(diǎn)出發(fā)，每次沿著要走的字符串往下走，若沒有則建立新節(jié)點(diǎn)。 假如所有字符串的長度之和為n，構(gòu)建這棵trie樹的時(shí)間復(fù)雜度為O(n)。 int root=1; int cnt=1; int p[i][j];//表示從i這個(gè)節(jié)點(diǎn)沿著j這個(gè)字符走，能走到哪個(gè)點(diǎn)，走不到就是0 char s[];//存儲(chǔ)字符串 for(int i=1;i<> { scanf('%s',s); int len=strlen(s); int now=root;//now表示走到的當(dāng)前節(jié)點(diǎn)，now的初始值為根節(jié)點(diǎn) for(intj=0;j<> { if(p[now][s[j]]>0){ now=p[now][s[j]];//如果能沿著j節(jié)點(diǎn)往下走，直接往下走 } else{ pow[now][s[j]]=++cnt; now=p[now][s[j]]; } } v[now]++;//記錄now這個(gè)節(jié)點(diǎn)被訪問的次數(shù) }
3.Trie樹的查詢： 可以看出trie樹中每個(gè)節(jié)點(diǎn)表示其中一個(gè)字符串的前綴，在做題過程中往往通過這個(gè)性質(zhì)來得到較好的時(shí)間復(fù)雜度。
4.一個(gè)例題： 給定n個(gè)互不相同的串，求存在多少對數(shù)(i,j)（共n2對）滿足第i個(gè)串是第j個(gè)串的前綴。 所有串的長度之和≤500000。 解題：根據(jù)性質(zhì)，“在樹上，兩個(gè)點(diǎn)u,v滿足u是v的祖先，那么u代表的字符串一定是v代表的字符串的前綴”。 我們要滿足一個(gè)串是另一個(gè)串的前綴，也就是說，在trie樹上，這個(gè)串對應(yīng)的位置是另一個(gè)串對應(yīng)的位置的祖先。 構(gòu)建這棵trie樹，然后我們枚舉每個(gè)紅色點(diǎn)，它對答案的貢獻(xiàn)是以它為根的子樹中紅色節(jié)點(diǎn)的個(gè)數(shù)之和。這個(gè)東西可以在一開始遍歷這棵樹預(yù)處理出來！ 時(shí)間復(fù)雜度是線性的。
void dfs(int x) { if(v[x]) sum[x]++; for(chari='a';i<> { if(p[x][i])//從當(dāng)前x沿著i這個(gè)字符走還能往下走 { dfs(p[x][i]);//往下走 sum[x]+=sum[p[x][i]];//累加貢獻(xiàn)sum } } } dfs(1);//從根節(jié)點(diǎn)開始 5.USACO的某題： 給定n個(gè)串，重排字符之間的大小關(guān)系，問哪些串有可能成為字典序最小的串。 所有字符串的長度之和<>。 例如，有一個(gè)字符串，里面只有'a'~'z'這些字符，默認(rèn)地，'a'是最小的，'z'是最大的。但是我們可以重新定義字符間的大小關(guān)系，比如這樣：b<><><><><>，從而我們對于一些字符串，就按照我們新定義的大小關(guān)系來比較字典序大小。 舉個(gè)栗子： 三個(gè)字符串'aab','aba','baa'，總共只出現(xiàn)了兩個(gè)字符'a'和'b'，所以字符間的大小關(guān)系要么是a<>要么是a>b，假設(shè)a<>，則第一個(gè)串'aab'就是字典序最小的串；假設(shè)b<>，則第三個(gè)串'baa'就是字典序最小的串，但是對于第二個(gè)串，無論我們怎么定義字符間的大小關(guān)系，都不可能成為三個(gè)字符串中字典序最小的。 解題：首先對這n個(gè)串構(gòu)建trie樹，之后對每個(gè)串，從根走向它，這個(gè)路程中遇到的所有兄弟在字典序下都比它大。 對于每個(gè)串，從前往后，直接確定這個(gè)字符的大小關(guān)系，判斷是否是字典序最小。 以下兩個(gè)串都是有可能成為字典序最小的串的： abcd…xyza abcd…xyzb 所以有：u是v的前綴，則v一定不是字典序最小的串。 現(xiàn)在問題來了：對于每個(gè)串，在什么條件下，是字典序最小的？？ 來個(gè)栗子：有一些字符串（'aabc'，'aac'，'aad'，'ac'，'adb'，'aabb'），構(gòu)造trie樹如下：
對于'aabc'這個(gè)串，往下遍歷： 從深度為2的那一層，我們可以得到：a<><>； 從深度為3的那一層，我們可以得到：b<><>； 從深度為4的那一層，我們還可以得到：c<>。 綜上所述：我們得到了一堆的關(guān)系：a<><>；b<><>；c<>，容易看出，這些關(guān)系是存在矛盾的，所以無解->'aabc'是不可能成為字典序最小的串。 所以要想有解，這一堆的關(guān)系必須滿足兩個(gè)條件：①不存在矛盾②不存在環(huán) 總的來說，就是判斷這一堆的關(guān)系是否存在拓?fù)湫颍?/span> 最多有26×26個(gè)大小關(guān)系，而最多有100000個(gè)字符串，所以時(shí)間復(fù)雜度最大為：O(26×26×100000)。
二、KMP算法
給定兩個(gè)字符串A,B，判斷T是否為S的子串（變式：尋找子串B在串A中的位置）。 要求一個(gè)O(|A|+|B|)的做法。 通常稱A為目標(biāo)串（或主串），B為模式串。 算法過程： 我們假設(shè)串A的長度為n，串B的長度為m，每個(gè)字符串的開頭下標(biāo)默認(rèn)為1。
定義兩個(gè)變量i和j，這兩個(gè)變量共同表示：A[i-j+1~i]與B[1~j]均匹配，即：A中以第i個(gè)字符結(jié)尾的、長度為j的字符串，和B從頭開始長度為j的字符串完全匹配。
繼續(xù)往下匹配：如果i+1和j+1不匹配。
現(xiàn)在，就是用到了KMP算法的核心：它對這一情況的處理方式是減少j，就相當(dāng)于將子串向右平移。 平移的目的是為了讓“A[i-j+1~i]與B[1~j]均匹配”這個(gè)條件重新滿足。 在上圖中，j一直減小到了0，因?yàn)橄蛴移揭频倪^程中，始終不能讓這個(gè)條件滿足（最右邊'?'部分已經(jīng)越界） 但有時(shí)候，將j減少一點(diǎn)點(diǎn)之后，是可以重新滿足條件的，例如：
那么我們將j從7減小到4時(shí)，有：
這樣就可以完全匹配啦！但是后面還有沒有匹配的機(jī)會(huì)我們就不管了，至少我們已經(jīng)保證A[4~7]和B[1~4]完全匹配上了。 現(xiàn)在考慮一個(gè)問題：我們每次把j減小1（一位一位地平移B字符串），這樣太慢了，我們在這里預(yù)處理一個(gè)next[]數(shù)組，表示當(dāng)j匹配不下去的時(shí)候，我們可以把j減少到next[j]，繼續(xù)嘗試匹配。 預(yù)處理過程：讓j自己和自己匹配一下，一旦匹配發(fā)現(xiàn)B[k-m+1~k] 和 B[1~m] 匹配，則說明在A與B匹配過程中，j等于k匹配不下去時(shí)，j可以嘗試減小到m。 過程如下：
/**************************************///靚麗的分界線
一些代碼：
/*核心內(nèi)容*/ for(int i=1,j=0;i<> { while(j&&B[j+1]!= A[i]) j=next[j]; if(B[j+1]==A[i]) j++; if(j==m) { printf('%d\n', i-j+1);//輸出找到的'B字串在 A中位置' //如果要求的是出現(xiàn)次數(shù)，這里也有可能是ans++什么的 j=next[j];//讓循環(huán)進(jìn)行下去 } }
for(int i=2,j=0;i<=m;i++)>預(yù)處理next[]數(shù)組*/ { while(j&&B[j+1]!=B[i]) j=next[j]; if(B[j+1]==B[i]) j++; next[i]=j; }
經(jīng)典例題：Blue jeans（POJ 3080） 給定m個(gè)串，求字典序最小的公共子串。找一個(gè)串，使得這個(gè)串是所有串的子串，并且字典序最小。 m≤10，每個(gè)串的長度≤60. 解題思路：一個(gè)串，如果是所有串的子串，那么肯定是第一個(gè)串的子串。 枚舉所有子串，復(fù)雜度為60*60。 驗(yàn)證其它串是否包含這個(gè)子串，復(fù)雜度為10*60。 每次更新答案即可。 時(shí)間復(fù)雜度為：O(603×10) 經(jīng)典例題：Seek the Name,Seek the Fame（POJ 2752） 給定一個(gè)字符串S，求所有既是S的前綴又是S的后綴的子串，從小到大輸出這些串的長度。 |S|<>。 N為字符串S的長度。
解題思路： 回到KMP算法，我們令P[j]表示找最大的數(shù)x，使得B中位置是1~x的字符與j-x+1~j的字符完全相同，也就是上面講的KMP算法中的next[]。 考慮P[|S|]的意義，也就是最大的前綴等于后綴的長度（不包括其本身）。 那P[P[|S|]]就是次大的。 因此所有P[P[…P[|S|]]]就是答案了，一直這樣遞歸下去就可以找到答案。 或者用Hash來做，這樣更容易想到也比較方便，但效率沒有KMP高。
三、AC自動(dòng)機(jī)
有n個(gè)模式串，長度之和是|T|，有一個(gè)主串，長度是|S|，問哪些模式串是這個(gè)主串的子串（或者有多少個(gè)模式串在主串中出現(xiàn)過）？ 解法一：直接跑n次KMP算法，時(shí)間復(fù)雜度：O(n×|S|)。 解法二：AC自動(dòng)機(jī)，時(shí)間復(fù)雜度：O(|T|+|S|)，對于n個(gè)串，構(gòu)建trie樹，在trie樹上做KMP。 在這里我來詳解一下AC自動(dòng)機(jī)啊~ 首先我們定義一個(gè)指針，叫做“失配指針”或者“失敗指針”，在KMP算法中，這個(gè)失配指針就是next[]數(shù)組，同樣地在AC自動(dòng)機(jī)中，在trie樹上也定義一個(gè)失配指針與此類似但不完全相同。 失配指針：假設(shè)一個(gè)節(jié)點(diǎn)k的失配指針指向j，那么k、j滿足性質(zhì)：設(shè)根節(jié)點(diǎn)root到j的距離為n，則從k以上的第n個(gè)節(jié)點(diǎn)到k這個(gè)節(jié)點(diǎn)所組成的長度為n的單詞，與根節(jié)點(diǎn)root到j所組成的單詞完全相同。 如下圖：
單詞'she'中的'e'的失配指針指向的是單詞'her'中的'e'，因?yàn)榧t框中的部分是完全一樣的。 然后，問題來了，我們該怎樣處理這個(gè)失配指針呢？其實(shí)我們可以用BFS就很方便地解決了。 處理過程：讓和根節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的失配指針指向根節(jié)點(diǎn)，對于其他節(jié)點(diǎn)（假設(shè)為a），設(shè)這個(gè)節(jié)點(diǎn)上的字母為ch，沿著a的父親b的失配指針走，一直走到一個(gè)節(jié)點(diǎn)c，c的兒子中也有字母為ch的節(jié)點(diǎn)d，然后把a節(jié)點(diǎn)的失配指針指向c節(jié)點(diǎn)的兒子d（因?yàn)?/span>d的字母也為ch），如果一直走到了根節(jié)點(diǎn)都沒找到，那就把失配指針指向根節(jié)點(diǎn)。 最開始，我們把根節(jié)點(diǎn)加入隊(duì)列(根節(jié)點(diǎn)的失敗指針顯然指向自己)，這以后我們每處理一個(gè)點(diǎn)，就把它的所有兒子加入隊(duì)列，直到搞完。 這樣我們就得到了一棵帶有失配指針的trie樹了，接下來正式介紹AC自動(dòng)機(jī)工作原理！ AC自動(dòng)機(jī)原理：對于一棵trie樹，我們用黃色表示一個(gè)單詞（某個(gè)模式串）的末尾，也就是說從根節(jié)點(diǎn)走到一個(gè)黃色的點(diǎn)，就組成一個(gè)“單詞”，如下圖：
一開始，trie樹中有一個(gè)指針t1指向根節(jié)點(diǎn)root，將這n個(gè)模式串合并為一個(gè)模式主串，模式主串中有一個(gè)指針t2指向這個(gè)模式主串的串頭。 接下來進(jìn)行類似KMP算法的操作：如果t2指向的字母，是trie樹中，t1指向的節(jié)點(diǎn)的兒子，那么把t2+1，t1改為那個(gè)兒子的編號(hào)，否則t1順這當(dāng)前節(jié)點(diǎn)的失配指針往上找，直到t2是t1的一個(gè)兒子，或者t1指向根為止。 如果t1經(jīng)過了一個(gè)黃色的點(diǎn)，那么以這個(gè)點(diǎn)結(jié)尾的單詞就算出現(xiàn)過了（這個(gè)模式串已經(jīng)在主串中出現(xiàn)了），或者如果t1所在的點(diǎn)可以沿著失配指針走到一個(gè)黃色的點(diǎn)，那么以那個(gè)黃色的點(diǎn)為結(jié)尾的單詞就算出現(xiàn)過了（這個(gè)模式串已經(jīng)在主串中出現(xiàn)了），記錄答案即可。
經(jīng)典例題：假裝是字符串的題——正則表達(dá)式 給定一個(gè)字符串，判斷其是否為合法的正則表達(dá)式。 一個(gè)正則表達(dá)式定義為： ①0是正則表達(dá)式，1也是正則表達(dá)式。 ②P和Q都是正則表達(dá)式，則PQ也是正則表達(dá)式。 ③P是正則表達(dá)式，則(P)是正則表達(dá)式 ④P是正則表達(dá)式，則P*也是正則表達(dá)式 ⑤P和Q都是正則表達(dá)式，則P|Q是正則表達(dá)式 舉個(gè)栗子： 010101101* (11|0*)* 以上都是都是正則表達(dá)式 |S|<> 解題思路：令dp[i][j]表示第i個(gè)字符到第j個(gè)字符能否組成正則表達(dá)式，分5種情況進(jìn)行轉(zhuǎn)移就可以了。
四、隨機(jī)算法
①隨機(jī)生成一棵樹：
for(int i=2;i<=n;i++)>隨機(jī)生成一棵樹*/ { cout<><'><><> }//深度為lgn
②隨機(jī)生成一棵長毛的鏈：
/*隨機(jī)生成一棵長毛的鏈：1~n/2*/ for(int i=2;i<=n ;i++)=""><><><> for(int i=n/2+1;i<=n;i++)><><><>
③給你一張圖，生成一張圖：
/*給你一張圖，生成一張圖，10萬個(gè)點(diǎn)，20萬條邊 */ map for(int i=1;i<> { int A=rand()%n+1; int B=rand()%n+1; while(A==B||mp[1ll*A*100005+B]) { A=rand()%n+1; B=rand()%n+1; } mp[1ll*A*10005+B]=1; cout<><><><> }
④隨機(jī)生成一個(gè)連通圖： 先生成一棵樹，這棵樹上的邊是一定存在的，在隨機(jī)其他的邊。 另：為感謝各位家長一直以來對融科信息學(xué)的信任與支持，在雙十二來臨之際，特推出雙十二底價(jià)團(tuán)購信息學(xué)課程，詳情點(diǎn)擊鏈接→融科教育雙十二同學(xué)“惠”，信息學(xué)課程底價(jià)瘋狂搶！（←點(diǎn)擊鏈接，了解活動(dòng)詳情吧） 長沙信息學(xué)競賽 |
|
|
