字符串的有關(guān)算法

字符串的相關(guān)算法還是在前面的話因為本人太弱…所以這幾天講的ppt經(jīng)常會發(fā)現(xiàn)錯誤，建議在ppt大略的基礎(chǔ)上去找相關(guān)論文學(xué)習(xí)?？赡苤攸c(diǎn)還是在原理的簡單解釋…有的地方聽不懂的話也沒關(guān)系，因為每個人沒有實現(xiàn)過代碼之前實際上都是這樣的，可能會對某些地方不理解不影響你對整個算法的印象。以后如果能夠?qū)ｉT思考的話也許就會快捷許多。字符串算法有一些的原理看起來比較麻煩，但是代碼量往往特別短，所以建議要去完全理解某個算法的原理，這樣子以后就算把模板忘了，也許也能夠通過原理寫出相應(yīng)的代碼。一開始可以學(xué)習(xí)一下練習(xí)模板。字符串算法的模板往往很短，很容易上手。大前天提到了分治…提到了這樣一個方程…f(n)=f(n/2)+f(n/2)+O(1)這個咱當(dāng)時是說f(n)=O(nlogn)那是咱SB…TooNa?ve考慮線段樹的節(jié)點(diǎn)，就是這個分布的…可是線段樹的節(jié)點(diǎn)個數(shù)是O(n)的這個的解顯然應(yīng)該是f(n)=O(n)在此表示歉意咱所知道的字符串算法Pascal的Pos函數(shù)…Hash哈希Kmp和擴(kuò)展KmpTrie樹AC自動機(jī)后綴樹，后綴數(shù)組(SA)，后綴自動機(jī)(SAM)Manacher算法亂搞最近新出來的：回文自動機(jī)(PAM)(太弱不會)。Hash哈希Hash應(yīng)該都知道…常用的Hash函數(shù)?首先直接把每一個字符的ASCII值加起來作為Hash值不取模的情況很容易沖突…常用的Hash，自己設(shè)一個X進(jìn)制(X>=你的字符集的大小-1，比如大寫字母有26個字母，字符集大小為26)然后咱們就有Hash=∑S[i]*X^(i-1)假設(shè)字符串長度為s，這個就可以在O(s)的時間內(nèi)算出來。顯然如果存的下最后的Hash值的話，每一個字符串的Hash值必定不相同。Q:為什么？實際上這種計算方法，每個字符串都是X進(jìn)制下的一個數(shù)，而Hash值就是這個X進(jìn)制的數(shù)轉(zhuǎn)十進(jìn)制的值，由于X進(jìn)制的數(shù)互不相同，顯然Hash值，即十進(jìn)制的數(shù)也互不相同。Q：那如果字符串長度過大，以致會爆怎么辦？取個模唄…Q：那如果兩個字符串不同Hash值取某個模最后相同怎么辦？取多個模唄…如果多個模的情況下都相同那么就是同一個字符串。Q：如果取多個模都相同呢？……首先，這個模是你自己定的，所以一般數(shù)據(jù)是沒辦法全部卡的。接著，由中國剩余定理，只要取到的每個模足夠大，那么最后也可以保證一定范圍內(nèi)的Hash值是一定的。Q：中國剩余定理是什么？以后講數(shù)學(xué)的時候會講吧…順便可以百度_(:зゝ∠)_除了這種Hash以外，字符串Hash也有很多其他的版本，比如ELFhash(黑書上的)據(jù)說這個的效果比上面的還好，咱沒試過_(:зゝ∠)_FunctionELFhash(vars:string):integer;Varg,h,i:longint;Beginh:=0;fori:=1tolength(s)dobeginh:=hshl4+Ord(S[i]);g:=hand$f0000000($是十六進(jìn)制)ifg<>0thenh:=hxor(gshr24);h:=hand(notg);end;ELFhash:=hmodM;End;Bzoj1014JSOI2008火星人火星人最近研究了一種操作：求一個字串兩個后綴的公共前綴。比方說，有這樣一個字符串：madamimadam，我們將這個字符串的各個字符予以標(biāo)號：序號：1234567891011字符madamimadam現(xiàn)在，火星人定義了一個函數(shù)LCQ(x,y)，表示：該字符串中第x個字符開始的字串，與該字符串中第y個字符開始的字串，兩個字串的公共前綴的長度。比方說，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函數(shù)的過程中，火星人發(fā)現(xiàn)了這樣的一個關(guān)聯(lián)：如果把該字符串的所有后綴排好序，就可以很快地求出LCQ函數(shù)的值；同樣，如果求出了LCQ函數(shù)的值，也可以很快地將該字符串的后綴排好序。盡管火星人聰明地找到了求取LCQ函數(shù)的快速算法，但不甘心認(rèn)輸?shù)牡厍蛉擞纸o火星人出了個難題：在求取LCQ函數(shù)的同時，還可以改變字符串本身。具體地說，可以更改字符串中某一個字符的值，也可以在字符串中的某一個位置插入一個字符。地球人想考驗一下，在如此復(fù)雜的問題中，火星人是否還能夠做到很快地求取LCQ函數(shù)的值。字符串長度始終<=10^5，操作數(shù)<=10^4題目是什么意思？一般先化成裸題。LCP是最長公共前綴，現(xiàn)給出一個字符串S，支持以下操作：1詢問LCP(x,y)，也就是原字符串從x開始的字符串和從y開始的字符串最長的公共前綴2修改，修改原S的一個字符3添加，在S的第X個字符后面添加一個字符。這個有什么做法？也是可以把問題分開來考慮，比如，怎么快速求LCP?Hash?考慮使用Hash來做實際上這里的LCP(x,y)的x,y所代表的字符串都是S的后綴考慮每一個后綴Suffix[i]，就是從S的第i個字符開始的后綴，它的Hash值就是Hash[i]=S[i]+S[i+1]*26+S[i+2]*26^2...然后Suffix[i]的某個前綴S[i..j]的Hash值怎么算？Hash=Hash[i]-Hash[j]*26^(j-i+1)預(yù)處理出所有后綴的Hash[i]以及26^k的話也就是說咱們能夠O(1)地求出每一個后綴的某個前綴的Hash值。之前又提到過一點(diǎn)：對于兩個相同的字符串，他們的Hash值相同，取模之后也相同。對于兩個不同的字符串，他們的Hash值不相同，但取模之后可能相同，模的數(shù)越大，同時取不同的模，最后相同的可能性越小。以這兩點(diǎn)作為依據(jù)，咱們可以這樣子做。對于詢問后綴X與Y的詢問，二分答案，即LCP的長度L，然后O(1)求出這個長度為L的前綴的Hash值，取不同的模，如果不同的模之后都相同，則可認(rèn)為這兩個長度為L的字符串相同，二分答案區(qū)間上移，否則則認(rèn)為不同，二分答案區(qū)間下移。這樣做的復(fù)雜度是O(logS)一次，S為字符串的長度。但是對于修改操作，咱們該怎么做？咱們可以發(fā)現(xiàn)，修改了字符S[i]，那么受到影響的就是它前面的所有字符的Hash值，對于前面來說這個改動比較大…而添加字符…對于所有的Hash值，都要重算…這怎么做啊，這沒法做啊…實際上還是可以做的…咱們以原字符串的順序建立平衡樹，每個節(jié)點(diǎn)i維護(hù)一個信息，就是它為根的子樹所構(gòu)成的字符串的Hash值和它為根的子樹的大小size。那么遞推式？Hash[fa]=Hash[lson]+s[fa]*26^(Size[lson])+Hash[rson]*26^(Size[lson]+1)然后這樣子就可以做了…每一次把一個后綴全部弄到一棵子樹里面，然后它的Hash值就是根節(jié)點(diǎn)的那個Hash值。這個得用Splay來做對于修改，直接在子樹上修改，然后再往根節(jié)點(diǎn)一路走，修改沿途的節(jié)點(diǎn)的Hash值。對于添加，直接Splay添加節(jié)點(diǎn)，然后往根節(jié)點(diǎn)走，每個節(jié)點(diǎn)的size+1,Hash值也更新。Splay一次的復(fù)雜度是O(logS)，所以一次的復(fù)雜度是O(logS*logS)，假設(shè)詢問q次，總復(fù)雜度就是O(qlogS*logS)P黨Splay比較吃力,咱blog有(別人的)AC代碼，實在A不了可以去看一看。Hash的實現(xiàn)：2行即可…(不算上預(yù)處理)上面所提到的Hash能夠在O(1)的時間判斷兩個串是否相同（如果預(yù)處理相應(yīng)的Hash值）。然后Hash不僅僅只可用于字符串，還可以用于某些狀態(tài)的壓縮以及O(1)的查找。比如上一次某道求某個數(shù)全部排列模m=0的數(shù)的個數(shù)的數(shù)位dp的，咱們暴力枚舉一半的排列a，然后將另一半的排列模m的值轉(zhuǎn)Hash，然后對于排列a，可以計算出為了模m=0另一半所需要的模值，然后O(1)可處理詢問。還比如廣搜，為了判斷某個狀態(tài)之前是否搜過，也可以設(shè)計一個函數(shù)做成Hash值。這些都是常見的運(yùn)用。接著提到的是字符串匹配問題…給你一個字符串S，一個字符串P，求P在S中出現(xiàn)了幾次。S長度為n，P長度為m。保證m<=n咱們所知道的算法…1.暴力算法,pos()+delete()…以上是檢驗這題是否是水題的標(biāo)準(zhǔn)2.Rabin-Karp算法。這是什么鬼？實際上就是剛才講的Hash…咱們對字符串P，可以用剛才X進(jìn)制的Hash函數(shù)，然后對于串P咱們有個Hash函數(shù)u，對于S的每個長度為m的子串，計算出一個Hash函數(shù)，總共有n-m+1個Hash函數(shù)，將它們和P的Hash函數(shù)u比較即可。然后計算S的n-m+1個Hash函數(shù)可以遞推。遞推式？（假設(shè)字符集大小為x）復(fù)雜度？O(n-m+1)。（還可以推廣到二維平面的字符串匹配!!）這么好的算法，為什么咱們竟然不知道？因為這里的Hash是取模的，取模之后有可能相同，而咱們這里要求的算法是100%正確，也就是說精確匹配，如果P和某個的Hash值不同顯然無視，可是如果相同的話還得從頭比較。（因為從取模的Hash值不能100%確定某個串一定等于另一個）這樣的話最壞n-m+1個都要比較，比較一次O(m),復(fù)雜度O(m(n-m+1))。這個算法最壞復(fù)雜度和暴力差不多…但是期望情況很好。3.有限狀態(tài)自動機(jī)匹配（這個后面ppt會提到，預(yù)計下次講了）這個的復(fù)雜度，設(shè)字符集大小為∑，那么復(fù)雜度建立字符串P的自動機(jī)O(m∑)，匹配O(n)。好處是自動機(jī)建立好之后，可以同時求多個串S中是否出現(xiàn)P。4.Knuth-Morris-Pratt算法也就是所說的KMP算法。1）KMP算法的原理？2）KMP算法復(fù)雜度的證明？3）能隨手敲一個KMP嗎？KMP算法其實不難理解。設(shè)這里有個S串一部分為ababaab，P串為ababaca，匹配到第六個字符的時候失效，這個時候咱們就想盡量利用已經(jīng)匹配到的信息?？紤]暴力做法是怎么樣的。暴力的做法就是右移一位，然后再從頭比較，但是咱們通過之前的匹配知道這里是不可能有匹配的。因為已經(jīng)匹配的部分ababaa的babaa的這個后綴和ababaa這個的公共前綴為0.所以這里還去匹配是不理智的。咱們發(fā)現(xiàn)這里的信息所涉及的串…好像只跟P有關(guān)…而這個暴力的過程，實際上就是拿P的第i個后綴和它的前綴繼續(xù)匹配。而如果這個后綴能夠匹配P的某個前綴，那么它就能繼續(xù)在失配的那個地方匹配下去。實際上就是求P已經(jīng)匹配的串p[1..i]的最大后綴，使得它是p[1..i]的公共前綴!而這個東西是只和P字符串有關(guān)…比如ababaa字符串，它的p[1..5]的最大后綴是[3..5]也就是aba,它和ababaa的前綴p[1..3]匹配。這個時候咱們直接將P移動到S的ababaa的第二個a處即可。這個時候已經(jīng)有3個字符被匹配了。所以咱們只要求P的每個前綴的最長的相同后綴就可以了。設(shè)這個后綴的長度是next[]next[i]的含義就是p[1..i]這個字符串的能夠匹配前綴的最大后綴的長度。幾個小練習(xí)來理解.abbabba的next[4]=?next[6]=?next[4]=1,next[6]=3.這個next[]函數(shù)理解了之后，考慮next[next[]]的含義？next[i]是p[1..i]這個字符串能夠匹配前綴的最大后綴的長度,也就是說p[1..i]里面p[1..next[i]]=p[i-next[i]+1..i]而且這個是最長的。那么next[next[i]]就是p[1..next[i]]這個字符串的能夠匹配前綴的最大后綴的長度，又由于p[1..next[i]]=p[i-next[i]+1..i]，所以這個可以理解為：能夠匹配p[1..next[i]]前綴的p[i-next[i]+1..i]的最大后綴的長度實際上這個又等價于匹配p[1..i]前綴的p[1..i]的第二大后綴。也就是說next[next[i]]表示的就是能夠匹配p[1..i]的前綴的第二大后綴的長度。那么next[next[next[i]]]?表示的就是能夠匹配p[1..i]的前綴的第三大后綴的長度。以此類推現(xiàn)在考慮求next[i]，假設(shè)已經(jīng)知道next[1],next[2],next[3],…next[i-1]。因為next[i-1]表示的是p[1..i-1]的匹配前綴的最長后綴。那么如果p[next[i-1]+1]=p[i]的話，那么顯然p[1..i]的匹配的最長前綴就是p[1..next[i-1]+1]了。這個時候next[i]=next[i-1]+1;如果p[next[i-1]+1]<>p[i]。咱們也沒關(guān)系。next[i]表示的是p[1..i-1]匹配前綴的最長后綴，咱們可以繼續(xù)去找第二長，第三長后綴…繼續(xù)去匹配。怎么做？之前提到了，假設(shè)第K長的后綴的長度是u，那么第K+1長的后綴的長度就是next[u]枚舉第K長后綴，判斷其對應(yīng)前綴+1的字符是不是s[i]，如果是的話，這個就是p[1..i]的匹配的最長前綴了。某個實現(xiàn)代碼如下：next[1]:=1;Fori:=2tomdoBeginj:=next[i-1];{其實不需要寫這句話，因為這個過程倒數(shù)第二行已經(jīng)有了這句話，這里標(biāo)上是為了強(qiáng)調(diào)}while(j>0)and(s[j+1]<>s[i])doj:=next[j];if(s[j+1]=s[i])inc(j);next[i]:=j;End； 代碼量也是極短的…以上是預(yù)處理。接下來是KMP算法的匹配。實際上比預(yù)處理簡單多了。假設(shè)匹配兩個字符，匹配得上，兩個都+1，這個顯然?？紤]匹配不上，假設(shè)這個時候是p[1..i]已經(jīng)匹配,p[i+1]和s[x]失配，咱們只需要沿著next[i]走，然后繼續(xù)匹配即可，如果走到0了還是沒能匹配，那么s[x]無論如何都匹配不了，接下來繼續(xù)匹配s[x+1]和p[1]。考慮P：abbabbaS：aaababbababbabbaba的匹配過程。最后就是復(fù)雜度證明了…先證明預(yù)處理的復(fù)雜度是線性的，也就是O(m)的考慮有哪些操作Fori:=2tomdowhile(j>0)and(s[j+1]<>s[i])j=next[j]if(s[j+1]=s[i])inc(j)next[i]=j咱們發(fā)現(xiàn)復(fù)雜度在于j的變化?？紤]j的增加，j最多增加m次，每次都加1?？紤]j的減少,由于j最后非負(fù),j減少肯定不超過m，考慮最壞情況j每次只減少1，那么最后也只減少m次，所以復(fù)雜度是O(m)線性的。Smartojp1848統(tǒng)計單詞數(shù)

一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計出特定單詞在文章中出現(xiàn)的次數(shù)。現(xiàn)在，請你編程實現(xiàn)這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。!!注意：匹配單詞時，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）。輸出單詞出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置(-1代表未出現(xiàn))單詞的位置從0開始ToTotobeornottobeisaquestion20(出現(xiàn)2次，第一次出現(xiàn)在0處）toDidtheOttomanEmpireloseitspoweratthattime-1單詞長度<=10文章長度<=10^6這道題不像普通的匹配，必須要求原文章的對應(yīng)字符是一個獨(dú)立的單詞。然而這并沒有什么…因為咱們可以找出一個單詞在原文章出現(xiàn)的所有位置，所以只需要每找到一個，判斷他是否是一個獨(dú)立的單詞就可以了。判斷是否是獨(dú)立的單詞，其實就是看這個字符串前面和后面是否是空格就可以了…一個獨(dú)立的單詞按照題目意思，必然是前后都是空格…問題解決。CHHSYOI2015Round2

E.字符串與KMP給你一個n<=10^6的字符串，求該字符串的最小循環(huán)節(jié)。循環(huán)節(jié)就是該字符串可由該循環(huán)節(jié)重復(fù)得到。比如abcabc的最小循環(huán)節(jié)是3，aaaaa的最小循環(huán)節(jié)是1.要做這道題請加入CH上華師一附中的小組，無需審核。求一個字符串的循環(huán)節(jié)…咱們和這道題的標(biāo)題相聯(lián)系…很容易想到KMP算法。但是KMP算法不是求字符串P和S的匹配么？這里才一個字符串？考慮next[]的含義，next[i]是p[1..i]的匹配前綴的最大后綴。設(shè)字符串P長度為n，那么next[n]含義？P[1..n]的匹配前綴的最大后綴。如果P是由一個最小循環(huán)節(jié)構(gòu)成的串，那么咱們能夠知道,p[next[n]+1…n]就是它的最小循環(huán)節(jié)。為什么？假設(shè)有K個最小循環(huán)節(jié)，那么顯然P[1..n]的最大后綴就是后K-1個循環(huán)節(jié)構(gòu)成的后綴。假設(shè)有更長的后綴，可以通過證明最小循環(huán)節(jié)內(nèi)部的字符全部右移X位不等于原字符得證。所以算法就是，求這個字符串的next[]，然后答案就是n-next[n];Noi2014動物園題目大意:給定字符串S，定義num[]，num[i]表示的是S的前綴S[1..i]的能夠匹配前綴的后綴的個數(shù)，且要求該后綴不能與匹配的前綴相重疊。求∏(1+num[i])S長度n<=10^6一組數(shù)據(jù)可能有多個(T個)字符串要求該值，T<=10考慮next[]的含義，next[i]正是S[1..i]匹配前綴的最大后綴，而next[next[i]]就是第二大，以此類推。那么對于每個i，咱們只要找到第一個next[next[..]]，滿足next[next[..]]<=i/2，那么這之后的都滿足答案。咱們考慮每個i走多少次走到盡頭，設(shè)這個次數(shù)為dist[i]，那么咱們就是要找到一個0<=j<=dist[i],使得它的長度小于等于i/2，顯然這是單增的…所以直接二分就可以了，復(fù)雜度O(logN)一次。最后的復(fù)雜度就是O(nlognT)，可以過。實際上考慮inext[i]看作一條邊的話，每個位置看作一個點(diǎn)的話，這顯然就是一個森林。所以上面的二分的方法其實就是樹上路徑的二分。出題者當(dāng)時憤恨地說，沒能卡掉logN真是可惜。這真是一個悲(Xi)傷(Gan)的故事也就是說這里還有更好的做法？咱們考慮定義一個新的數(shù)組Next[]，Next[]數(shù)組類似next[]，Next[i]表示S[1..i]中匹配前綴的最大后綴，且這個后綴和前綴不重合?？紤]已經(jīng)求出了Next[1],Next[2]….Next[i-1],現(xiàn)在要求Next[i]，咱們類似next[]的做法，先令j=Next[i-1],然后考慮S[j+1]=S[i]?然后還要判斷是否超界，如果超界，貪心的咱們就繼續(xù)往next[j]走即可。這樣的復(fù)雜度和Kmp是一樣的是O(n)的。Q：為什么不在求next[]的時候一起求Next[]?因為求Next[]的時候如果在求Kmp的時候回去找，實際上就相當(dāng)于每一次都暴力從某個節(jié)點(diǎn)沿著樹往根走，這和暴力沒啥區(qū)別。而后面的類似Kmp的Next[]的求法則是從上一次Next[]作為起點(diǎn)的，可以用類似Kmp復(fù)雜度證明的方法證明它也是線性的（這題可見掌握Kmp算法的原理和復(fù)雜度的證明有多么重要）Smartojp2168

[Clover9]外星人外星人有n只眼睛，排成一排，從左到右標(biāo)號為1ton.他睡覺的時候會給自己帶上眼罩，每個眼罩的內(nèi)側(cè)都有一個大寫字母。當(dāng)他早上起來睜開眼睛時，他想看到beautifulwords.外星人還有一個習(xí)慣就是，睜眼時他會選擇四個數(shù)字a,b,c,d,(1<=a<=b<c<=d<=n)，他將睜開在a<=i<=b和c<=i<=d這個范圍內(nèi)的所有眼睛。設(shè)一個beautifulword為字符串s，并且把外星人從左到右看到的字母按順序拼接成一個字符串串t，如果s和t相同，那么我們認(rèn)為外星人能夠看到s這個beautifulword。你知道他心目中有m個beautifulword。請問在他現(xiàn)在帶這個眼罩，任意選擇a,b,c,d四個數(shù)字的時候，他睜開眼可能看到的beautifulword有多少個？

首先看到一道題目要學(xué)會轉(zhuǎn)化成裸模型給你一個長度為n的字符串S，和m個字符串P[i],現(xiàn)在從S中截取s[a,b]+s[c,d](1<=a<=b<c<=d<=n)組成一個新的字符串，求所有的截取方案中和m相同的字符串有多少個？栗子：ABCBABA(s)2個Beautifulwords:BAAB，ABBA輸出1個，這1個是AB+BA得到的。S長度n<=10^4,m<=100首先容易想到的是暴力法。咱們枚舉[a,b][c,d]，然后去比較這個連起來的串和M個串，每一次的復(fù)雜度是O(M個串的長度+M*(a,b,c,d)串的長度)。優(yōu)化的話，甚至可以用Hash做，可以降到O(M)但是這里因為長度太長了，Hash很容易沖突，多次取模也有可能沖突。而即使不沖突，枚舉[a,b][c,d]也需要O(n^2)的時間，復(fù)雜度O(n^2*m)也會TLE掉…一種常見的思路就是先想出一個暴力算法，然后思考這種算法哪里慢了，想辦法優(yōu)化它。這里實際上咱們做了很多無用功。咱們枚舉S的斷點(diǎn)來判斷M是否相等，其中不可能是答案的斷點(diǎn)太多了，不如反過來思考，咱們可以這樣子做。咱們首先可以分開做，每一次只考慮其中一個串P在原S是否可能出現(xiàn)。咱們枚舉P的斷點(diǎn)，然后對兩個斷點(diǎn)做Kmp，這樣子咱們會發(fā)現(xiàn)咱們的答案的狀態(tài)比原來少了。每一次枚舉的復(fù)雜度是O(N^2)的。枚舉斷點(diǎn)的復(fù)雜度總的是O(MN^2)的做Kmp，一次O(N)然后M個的話，復(fù)雜度就是O(MN^3)的。好像比之前的Hash的方法要好…因為M較小，但是它是一個可以保證正確性的算法…但是貌似還是會TLE？怎么繼續(xù)優(yōu)化？哪里還是慢了？容易發(fā)現(xiàn)，能夠優(yōu)化的地方就只有枚舉斷點(diǎn)的O(N^2)了…這里顯然太慢了…在這個基礎(chǔ)上還要做Kmp，O(n^3)，顯然可以優(yōu)化。咱們用P給S做Kmp，記錄下S的每個節(jié)點(diǎn)為末端的，能夠匹配的最大長度f[i]。咱們發(fā)現(xiàn)，如果f[i]>0,f[i]=f[i-1]+1。這樣就可以通過f[]得到能夠枚舉出來的所有前面一截字符串了。但是后面一截怎么處理？斷點(diǎn)的后面一截實際上可以這樣處理。將P和S都倒過來，然后再做上面的Kmp，求出一個類似的函數(shù)g[]那么這個可以得到后面一截的那么只需要找到一個f[i]+g[j]=m且i<j即可。而又由于存在f[i]=m，那么f[i-1]=m-1,…f[i-k]=m-k。g[]類似，那么只需要找到一個f[i]+g[j]>=m，且i<j即可。之前的處理是O(n)沒有枚舉斷點(diǎn)，這里怎么做到也是O(n)?咱們發(fā)現(xiàn)，咱們可以枚舉j，然后對于每一個g[j]，找之前最大的一個f[i]即可。即對于每一個j，咱們設(shè)b[j]表示之前最大的f[i]，這個只要掃一遍就可以O(shè)(n)做到，然后枚舉g[j]，那么咱們就只要判斷b[j]+g[j]>=m是否成立即可，如果成立，那么就存在這樣一種斷點(diǎn)。這樣子做復(fù)雜度是O(n)的，而原來的復(fù)雜度是O(nm)的。這樣最終復(fù)雜度就是O(nm)字符串算法往往代碼量少，但是想法有時候難以想出。但一旦想出，基本上后面都很簡單，直接上模板，而模板基本上都很短。Timetorelax。接下來提到的是擴(kuò)展kmp首先是問題：給出一個字符串S(長度為n)和一個字符串P(長度為m)，求字符串S的所有后綴suffix[i]與字符串P的最長公共前綴，其長度記作ex[i]。比如S=aaaaab和P=aaaaaex[1]=5,ex[2]=4,ex[3]=3,ex[4]=2,ex[5]=1,ex[6]=0擴(kuò)展kmp算法可以在O(n+m)時間求出ex[i]思想是類似的，假如咱們求出了ex[1],ex[2]….,ex[n-1]，現(xiàn)在要求ex[n]首先[j,j+ex[j]-1]就是從j開頭的后綴和P的最大公共前綴。j+ex[j]-1就是這個最大公共前綴的末尾。[j,j+ex[j]-1]同時也是P的長為ex[j]的前綴。設(shè)j+ex[j]-1是所有的i+ex[i]-1最大的，也就是右邊界最遠(yuǎn)的。假設(shè)n<=j+ex[j]-1.也就是說n所在的字符串在[j,j+ex[j]-1]這個字符串以內(nèi)。也就是在P的長為ex[j]的前綴里面那么問題其實又是只牽扯到p了。由于這里S[j..j+ex[j]-1]=P[1..ex[j]]而n在[j,j+ex[j]-1]里面則有S[n..j+ex[j]-1]=P[n-j+1..ex[j]]n到最遠(yuǎn)的邊界有S[n..j+ex[j]-1]=P[n-j+1..ex[j]]而咱們要求的是S從n開始有多少長度等于P的前綴，也就是P[n-j+1..ex[j]]與P的前綴的最長公共前綴。咱們發(fā)現(xiàn)這類似Kmp，最后總會歸結(jié)為P自己的一個類似的問題。這里最后歸結(jié)的問題就是，求P的后綴和P的最長公共前綴。不妨設(shè)這個的答案數(shù)組為next[]假設(shè)咱們已經(jīng)求出所有的next[]，考慮剛才那個問題，已經(jīng)有S[n..j+ex[j]-1]=P[n-j+1..ex[j]]考慮next[n-j+1]=L那么就有P[1..L]=P[n-j+1..n-j+L]=S[n..n+L-1]如果有n+L-1<=j+ex[j]-1，可以看做n+L<j+ex[j]，那么咱們知道ex[n]就是L，因為之后的根據(jù)next[]的定義不可能相同，所以之后不可能還有更長的公共前綴。ex[n]=L如果n+L>=j+ex[j]，那么就要從j+ex[j]即最遠(yuǎn)邊界+1的位置開始和P[j+ex[j]-n]匹配,這里暴力即可。然后更新最大的j+ex[j]-1，如果n+ex[n]-1>j+ex[j]-1則更新。這樣就可以求出所有的ex[]了。那next[]怎么求？這個實際上就是P和P自己的擴(kuò)展Kmp類似Kmp的，已知next[1]…next[i-1],求next[i]。咱們發(fā)現(xiàn)P和S的擴(kuò)展kmp的求法可以套用到這里面。而且，這里的next[]是已知的，在計算第n個后綴的next[]，只需要用到之前的next[n-j+1]。這樣就完全解決了。考慮復(fù)雜度？復(fù)雜度的地方在于最遠(yuǎn)處的移動，而這個移動最多是O(字符串的長度），因此計算next[]和ex[]的復(fù)雜度就是O(n+m)，這就是擴(kuò)展kmp關(guān)于代碼？因為咱太弱了以前沒有寫過擴(kuò)展Kmp，只是理解了，所以不能給出一個保證正確的代碼_(:зゝ∠)_擴(kuò)展kmp的這個匹配過程可能麻煩的是位置，得仔細(xì)想一想位置。不過咱沒有用過擴(kuò)展kmp做過題目，題目做得太少見諒…不過多掌握一個算法總比沒有好。Timetohaveabreak_(:зゝ∠)_最后提一個Manacher算法（馬拉車算法）它的用途是用于O(n)求出一個長度為N的字符串以每一個字符為中心的能得到的回文串的長度。首先Manacher算法只能求奇數(shù)回文串，因為它每一次都只是枚舉其中一個字符作為對稱中心。那么偶數(shù)回文串怎么辦？在每兩個相鄰字符間添加相同的不屬于原字符集的符號即可。比如wshjzaa，處理就是插入“#”，那么就變成了#w#s#h#j#z#a#a#，這里原來的偶數(shù)回文串a(chǎn)a就變成了奇數(shù)回文串#a#a#這里的處理最多添加O(n)個字符，所以不影響最后復(fù)雜度。Manacher算法定義了這樣一個數(shù)組p[]，p[i]表示從字符i向左右延伸構(gòu)成回文串的最大長度。比如剛才的#w#s#h#j#z#a#a#p[]數(shù)組該如何表示?這里的p[1]=1,p[2]=2,p[3]=1,p[4]=2,p[5]=1,…….p[13]=3那么還是類似Kmp的那個遞推的思想，假設(shè)咱們已經(jīng)知道了p[1],p[2]…p[n-1],現(xiàn)在要求p[n]，如何求？類似擴(kuò)展Kmp，設(shè)p[1]~p[n-1]中的所有回文串中右端點(diǎn)最遠(yuǎn)的是p[i]+i-1，不妨標(biāo)記為right=p[i]+i-1；那么如果n<right的話，那么顯然n在[i,right]間。那么由于[i,right]是回文串的一半，所以它也有對稱的另一半[left,i]。而n在另一半也有一個對稱點(diǎn)n’而n’的p[]是已經(jīng)求出來的。如果n+p[n’]-1<=Right的話，那么顯然p[n]=p[n’]（假設(shè)p[n]>p[n’]，這與n與n’對稱的那一部分矛盾了）如果n+p[n’]-1>Right的話，那么就有p[n]=Right-n+1，即n到Right這一段是最長回文串，因為n’所在的回文串能超過Left，對應(yīng)過來則n所在的回文串不能超過Right，因為假如超過Right的話i的回文串的邊界就不是Right了。而上面兩種情況都是考慮n<=right的情況。實際其實只要寫p[n]=min(p[n’],right-n+1)即可。但是n>right的怎么辦？沒辦法…直接按定義來暴力。這個的復(fù)雜度？咱們可以發(fā)現(xiàn)，right是單調(diào)遞增向右的，而right向右只有可能是通過暴力這里才能向右，而right最多向右移動O(n)的距離，所以暴力的復(fù)雜度是O(n)的。而其余操作的復(fù)雜度是O(1)的。所以最終的復(fù)雜度就是O(n)的。Manacher算法的思想實際上和擴(kuò)展Kmp非常相像，都是設(shè)置了一個最遠(yuǎn)的右端點(diǎn)，然后右端點(diǎn)內(nèi)部的點(diǎn)通過某些性質(zhì)更新答案，而超出的就暴力更新，由于右端點(diǎn)單調(diào)遞增，所以暴力的復(fù)雜度也就是O(n)的。對了，咱們最后求出的p[]數(shù)組是加了#的字符串的，那么原字符串的呢？這里有個式子，新的字符串每一個字符i都對應(yīng)一個長度為p[i]-1的回文串，這個回文串以該字符為中心（如果這個字符是#的話就是偶數(shù)回文串）可見manacher還可以區(qū)分偶數(shù)和奇數(shù)長度的回文串!Hdu3608最長回文給出一個只由小寫字母字符a,b,c,…z,組成的字符串S，求S中最長回文串一個測試點(diǎn)有多組測試數(shù)據(jù)，保證不超過120組，字符串長度<=110000Manacher裸題…直接做建議用C++寫…Hdu對P不友善。Bzoj2160拉拉隊訓(xùn)練艾利斯頓商學(xué)院籃球隊要參加一年一度的市籃球比賽了。拉拉隊是籃球比賽的一個看點(diǎn)，好的拉拉隊往往能幫助球隊增加士氣，贏得最終的比賽。所以作為拉拉隊隊長的楚雨蕁同學(xué)知道，幫助籃球隊訓(xùn)練好拉拉隊有多么的重要。拉拉隊的選拔工作已經(jīng)結(jié)束，在雨蕁和校長的挑選下，n位集優(yōu)秀的身材、舞技于一體的美女從眾多報名的女生中脫穎而出。這些女生將隨著籃球隊的小伙子們一起，和對手抗衡，為艾利斯頓籃球隊加油助威。一個陽光明媚的早晨，雨蕁帶領(lǐng)拉拉隊的隊員們開始了排練n個女生從左到右排成一行，每個人手中都舉了一個寫有26個小寫字母中的某一個的牌子，在比賽的時候揮舞，為小伙子們吶喊、加油。雨蕁發(fā)現(xiàn)，如果連續(xù)的一段女生，有奇數(shù)個，并且她們手中的牌子所寫的字母，從左到右和從右到左讀起來一樣，那么這一段女生就被稱作和諧小群體?，F(xiàn)在雨蕁想找出所有和諧小群體，并且按照女生的個數(shù)降序排序之后，前K個和諧小群體的女生個數(shù)的乘積是多少。由于答案可能很大，雨蕁只要你告訴她，答案除以19930726的余數(shù)是多少就行了。K<=10^12，n<=10^6廢話太多…一般都想辦法轉(zhuǎn)化到裸模型來。題目大意：給出一個長度為n字符串，把所有以i為中心的奇數(shù)長度回文子串按長度降序排序，取前K個，求前K個的長度的乘積。首先…怎么才能只求出奇數(shù)長度的回文串？考慮以非#的字符作為中心就可以了。然后只需要把所有的p[]快排一遍，然后從大往小拿即可。復(fù)雜度O(nlogn)但是拿的時候…實際上可能有O(n^2)個…直接拿的復(fù)雜度可能會達(dá)到O(n^2)然而這并不難…咱們可以發(fā)現(xiàn)長度為k的答案就是大于等于k的回文串的個數(shù)。這個可以對O(n)的p[]使用cnt[]數(shù)組計數(shù)，cnt[i]表示p[]=i的有多少個，然后從大往小掃,對于長度為i的回文串的個數(shù)的答案就是cnt[i+1]+cnt[i+2]…+cnt[n+1]；這個顯然從后往前做，就是后綴和，復(fù)雜度O(n)然后用快速冪算即可。Bzoj2565最長雙倍回文串題目大意：給出一個字符串，求最長雙倍回文串。雙倍回文串就是對于一個串，如果它能劃分為X,Y而X,Y都是回文串，那么這個串就是雙倍回文串。給出字符串長度2<=n<=10^5舉例baacaabbacabb答案是aacaabbacabb，可分解為aacaa和bbacabb。Manacher可以搞單個回文串，現(xiàn)在問題是雙倍回文串如何搞…考慮咱們已經(jīng)搞出了p[]數(shù)組。雙倍回文串就是枚舉兩個加了#的新字符串的位置i,j(i<j)，滿足j-i+1<=p[i]+p[j]，從中間選j-i+1最大的就可以了。這個東西能用平衡樹來做….然而以上是一年沒做題的咱(嘴巴選手)看到題目的想法…其實上面的方法難寫而且復(fù)雜度沒有下面的好…咱們可以枚舉中間的分界點(diǎn)mid（就是#），然后咱們要求的就是回文串能覆蓋到mid的最小的j。這個設(shè)為min[mid]，類似的還可以設(shè)一個從右邊覆蓋mid的最大的i，設(shè)為max[mid]，那么咱們只需要枚舉mid,答案就從(max[mid]-min[mid]+1)*2中取最大即可現(xiàn)在問題是min[],max[]怎么求。顯然咱們可以發(fā)現(xiàn)，min[]是單調(diào)遞增的。這個的證明蠻容易，設(shè)i<j而min[i]>min[j]，可發(fā)現(xiàn)取min[j]的回文串也能覆蓋到i，而答案更優(yōu)。利用單調(diào)性做就可以了。復(fù)雜度O(n)加強(qiáng)版：Bzoj2342雙倍回文給出一個字符串,求最長雙倍回文。看起來和上一題相同？Naive.這里的雙倍回文要求，字符串長度能被4整除，字符串是回文串，而該字符串又可以平均分成兩半，每一半又是一個回文串。字符串長度N<=5*10^5首先咱們還是知道怎么做單個回文串。問題是這里的雙倍回文。先來看看雙倍回文的條件,考慮有一個S[i]=#,設(shè)其最長回文串的左端點(diǎn)為left=i-p[i]+1,而在[(left+i)/2,i]內(nèi)有一個j滿足j+p[j]-1>=i且S[j]=‘#’，且j盡量地小，由于對稱性，顯然由于i回文串對稱性另外一邊也會有一個對稱的回文串，這樣組成的就是雙倍回文。如果直接做…會發(fā)現(xiàn)只能暴力…或者這樣子…類似上一道題嘴巴選手的做法…求一個滿足下列條件的盡量小的jj+p[j]-1>=i,且(left+i)/2<=j而對于這個，咱們發(fā)現(xiàn)將j+p[j]-1排好序并且i按從大到小的順序枚舉，那么涉及到的j也就是單調(diào)的，然后只需要找這些j里面的最小的j>=(left+i)/2，這個用平衡樹可以做。這個的復(fù)雜度是O(nlogn+n),C++的SET可以實現(xiàn)然而pascal卻沒有set…使用set蒙蔽了大多數(shù)選手的雙眼…這一題真正精彩的地方不是用set直接水過…這里有一個性質(zhì)，對于bian=(left+i)/2，原來的j的區(qū)間是[bian,i]，可能有許多i和它們對應(yīng)的left都會計算出一個相同的bian，這是，而對于相同的bian，咱們可以發(fā)現(xiàn)，隨著i的增長，這個最后的答案j是單調(diào)遞增的。咱們給每一個bian都存下它最后一次得到的答案。而且如果某個答案j不符合答案，那么咱們可以把邊界縮小為[j,i]，然后咱們發(fā)現(xiàn)可以用j的答案繼續(xù)來更新。這是因為隨著i的增長最后的答案是單調(diào)的，所以之前的那些都可以拋棄。這個有點(diǎn)像…并查集？咱們p黨可以用并查集維護(hù)這個單調(diào)的答案?？墒沁@里面的父親是固定方向的，因此不能用按秩合并，所以復(fù)雜度和平衡樹一樣是O(nlogn)和原來的平衡樹的做法比起來代碼顯然更短(pascal上)這道題的單調(diào)性可能比較難理解，如果不理解可以去咱的blog看代碼，結(jié)合代碼的話可能更好理解。Manacher算法其實很簡單，所以大部分有關(guān)題目都不只是Manacher。這時候需要更加大的腦洞（大霧）其實Apio2014好像有提到，所以還是得重視一下馬拉車算法Todayisend有限狀態(tài)自動機(jī)關(guān)于字符串匹配那里提到了用這個來做…自動機(jī)就是這樣一個東西…它是由五個元素構(gòu)成的字符集∑一個非空的有限狀態(tài)集合Q起始狀態(tài)Start∈Q非空接受狀態(tài)End∈Q轉(zhuǎn)移函數(shù)f()自動機(jī)的基本工作原理是這樣。按順序讀入一個字符串的每一個字符，從起始狀態(tài)開始，然后根據(jù)轉(zhuǎn)移函數(shù)f(當(dāng)前字符，當(dāng)前狀態(tài))算出一個狀態(tài)，移動到那個狀態(tài)。當(dāng)讀完所有的字符，如果最后到達(dá)的狀態(tài)是接受狀態(tài)，那么就認(rèn)為這個自動機(jī)接受這個字符串。否則則認(rèn)為這個自動機(jī)不接受這個字符。所有能被有限狀態(tài)自動機(jī)M接受的串的集合稱為M的語言。基本上要理解的就這幾個。而這個東西可以用來做匹配。具體可以找JZP的《有限狀態(tài)自動機(jī)》和WC2014的喬明達(dá)神犇的《有限狀態(tài)自動機(jī)》來看看?，F(xiàn)在舉這些里面的兩個例子。這個自動機(jī)是用來做什么的？我們會發(fā)現(xiàn)，它只有讀入多個0之后讀入一個1的話，才可以走到終止?fàn)顟B(tài)q2實際上，該自動機(jī)的作用就是識別某個串是否有01這個子串。如果有01子串，則該串被自動機(jī)接受，否則不接受。這個是用來做什么的？注意到每次分別讀入3個1，就會走到終止?fàn)顟B(tài)，也就是說，原串有3的倍數(shù)個1的話，就會被接受。這個是用來判斷某個串的1的個數(shù)是不是3的倍數(shù)的自動機(jī)。比如111是被接受，01不接受。自動機(jī)一旦建好，判斷某個串是否具備某個性質(zhì)，只要在自動機(jī)上走一遍就可以了。這也是自動機(jī)方便的地方。于是我們可以考慮使用有限狀態(tài)自動機(jī)來匹配字符串。也就是說，建立字符串T的自動機(jī)，使得所有包含T的字符串能夠被該自動機(jī)接受，而不包含T的字符串則不能被接受。那么問題在于怎么建立這樣的自動機(jī)？這個說實話已經(jīng)不需要掌握_(:зゝ∠)_，只是讓各位了解一下自動機(jī)的一些基本性質(zhì)就可以了。這個的算法在算法導(dǎo)論的第32章有提到，但復(fù)雜度沒有Kmp好，預(yù)處理為O(n∑)其實上面所提到的自動機(jī)的概念也是為了引出下面幾種和字符串有關(guān)的數(shù)據(jù)結(jié)構(gòu)：AC自動機(jī)要聊到AC自動機(jī)就得先講Trie樹。Trie樹又叫字典樹。它的每條邊都代表一個字符，它從根節(jié)點(diǎn)開始往下走，走到某一個節(jié)點(diǎn)，經(jīng)過的路上的邊的字符連成一個字符串S，這個字符串S就是該節(jié)點(diǎn)所代表的字符串。顯然，根節(jié)點(diǎn)代表的字符串就是空串。Trie樹一般只要求兩個操作，一個是往Trie樹里面插入一個字符串，一個是查詢Trie樹里面是否有某個字符串。插入字符串很簡單，按位一個個字符插入就可以了，假設(shè)現(xiàn)在走到了節(jié)點(diǎn)i，要插入的字符是’a’，那么就先檢查節(jié)點(diǎn)i的’a’邊是否連有兒子j，如果有，就走到j(luò)，繼續(xù)插入下一個字符，如果沒有，就新建一個節(jié)點(diǎn)j，將節(jié)點(diǎn)i的’a’邊連向j，然后走到j(luò)繼續(xù)插入下一個字符。而查詢只要按位一個個字符走下去就可以了，如果走到某一個節(jié)點(diǎn)i，接下來的字符比如是’a’，而若’a’連向了一個兒子j,則走到j(luò)，繼續(xù)重復(fù)上面操作，兒子不存在的話，則說明原Trie樹沒有這個單詞，返回。Trie樹的時間復(fù)雜度，設(shè)插入的字符串的長度為n,則插入的復(fù)雜度是O(n)設(shè)查詢的字符串的長度為n，則查詢的復(fù)雜度就是O(n)，當(dāng)然如果Trie樹最深深度m<n的話，那么復(fù)雜度就是O(m)Trie樹實際上有一個很棒的思想，那就是動態(tài)開節(jié)點(diǎn)，一開始的Trie樹只有一個根節(jié)點(diǎn)，而每次插入字符串，如果當(dāng)前走不下去了，就新建一個節(jié)點(diǎn)，這樣子的話空間復(fù)雜度就和插入的字符串的長度有關(guān)了。也就是說，對于問題沒有涉及到的路，咱們不開設(shè)相應(yīng)的內(nèi)存，每次問題涉及到一個新的從前沒有的路，咱們臨時開辟內(nèi)存。這個思想也可以用于線段樹。一開始的線段樹只有一個大區(qū)間[0,n]，然后每一次涉及到一個區(qū)間[p,q]的操作，咱們只臨時建立和[p,q]相關(guān)的區(qū)間的節(jié)點(diǎn)。這個思想可以對付一些可能區(qū)間[0,10^9]，而實際上涉及到的區(qū)間只有10^5等很小的數(shù)量級的問題。Poj2418HardwoodSpecies題目大意：給出n個字符串(n<=10^6)，每個字符串長度不超過30，有可能有相同的字符串存在，不同的字符串最多10000種。統(tǒng)計不同種類的字符串出現(xiàn)的次數(shù)，并按照字典序排序后輸出。比如：ACABA出現(xiàn)了2次，B出現(xiàn)了1次，C出現(xiàn)了一次按照順序應(yīng)輸出211我們建立Trie樹，每次都插入一個新的字符串。那么怎么統(tǒng)計個數(shù)呢？咱們給每一個節(jié)點(diǎn)設(shè)一個信息域num[],表示該節(jié)點(diǎn)所代表的字符串有多少個，然后每次插入一個字符串走到終點(diǎn)，將終點(diǎn)節(jié)點(diǎn)的num[]+1然后按字典序走邊，遍歷一遍就可以了…復(fù)雜度？O(輸入字符串總長度)空間復(fù)雜度也是的。CFRound#311div2E

AnnandHalf-Palindrome

簡要翻譯：定義半回文串S，長度為n,就是滿足以下條件的字符：對于所有滿足以下條件的第i位：1）i為奇數(shù)2）i<=(n+1)/23）有S[i]=S[n-i+1]。那么則稱該字符串S為半回文串?，F(xiàn)給出一個長度為N的字符串S，S的所有子串中是半回文串的按字典序從小到大排成一列，求出第K小的半回文串。這里的字符只有a,b兩個N<=5000嗯..看起來問題有兩個，怎么求半回文串，以及怎么求第K小的半回文串。首先關(guān)于半回文串，manacher什么的算法是做不了了…但是咱們發(fā)現(xiàn)咱們好像直接暴力也可以哦…咱們可以這樣，枚舉一個字符作為中心點(diǎn)(奇數(shù)串半回文串)，或者枚舉兩個字符作為中心點(diǎn)(偶數(shù)半回文串)，然后暴力向兩邊擴(kuò)展，擴(kuò)展的復(fù)雜度最多是O(n^2)的，這里的n只有5000，顯然直接暴力就可以了，沒必要想什么麻煩的算法…當(dāng)然想出更優(yōu)秀算法的同學(xué)就可以出題啦這里的實現(xiàn)可以考慮用f[i][j]表示S[i..j]是不是半回文串，布爾變量存儲即可。然后考慮的問題是如何求第K大？咱們可以把所有的可能的半回文串插入一棵Trie，然后對于每一個節(jié)點(diǎn)維護(hù)一個sum[]表示的是以該節(jié)點(diǎn)為根的子樹所包含插入的字符串?dāng)?shù)，然后咱們就可以類似二叉樹查找的做了!假設(shè)從根節(jié)點(diǎn)出發(fā)，找第8小的字符串，而a邊的兒子連的節(jié)點(diǎn)sum[]=6,那么咱們就沒必要去a邊尋找，答案肯定往b走，以此類推。然后這樣子做就可以在O(n)找到答案了。但是!這里咱們要插入的字符串的個數(shù)最多有O(n^2)個，每個字符串的長度是O(n)的，復(fù)雜度可以達(dá)到O(n^3)的插入?！?.算法不優(yōu)秀的時候，咱們考慮一下這個算法哪里是不是算了重復(fù)的東西…顯然算了!比如有兩個字符串a(chǎn)baa和abaaaaa是半回文串，咱們可以在插入abaa的基礎(chǔ)上，插入abaaaaa的剩下的aaa。咱們可以這樣子做，每一次都插入S的一個后綴Suffix[p]，然后插入到第i個字符的時候，判斷f[p][p+i-1]是不是true，如果是的話那么這個節(jié)點(diǎn)就存在一個單詞，sum+1，否則繼續(xù)下去。然后再從下往上遞推更新sumSum[fa]=sum[l]+sum[r]+sum[fa];這樣子復(fù)雜度就還是O(n^2)了。這題就可以A了。Bzoj2741【Fotile模擬賽】【L】題目大意：主席想要拯救世界，于是他想在線詢問區(qū)間最大xor和翻譯題目：這題是主席出的，給你一個長度為N的數(shù)組A，然后每次詢問一個區(qū)間[l,r]里面的一個最大xor和序列，也就是求出一個i,j使得i<=j,且i,j在[l,r]內(nèi)，且A[i]xorA[i+1]xorA[i+2]…xorA[j]的值最大。N<=12000,詢問數(shù)m<=6000強(qiáng)制在線。時限1.5s先考慮一個簡單版本的做法，求區(qū)間[1,n]的最大xor和。這個怎么做？首先要知道兩個性質(zhì)axora=0和0xora=a咱們考慮O(n)求出前綴xor和s[i]S[i]=a[1]xora[2]xor….xora[i]那么區(qū)間[i,j]的xor和怎么表示？S[i-1]xorS[j]因為(a[1]xor…xora[i-1])xor(a[1]xor..xora[i-1]xor…xora[j])=a[i]xora[i+1]..xora[j]咱們考慮O(n)求出了前綴xor。咱們枚舉右端點(diǎn)j，現(xiàn)在的問題就是，要在0~j-1里面找出一個i使得s[i]xors[j]最大。這個怎么做？考慮xor的性質(zhì)，是按位異或。咱們把S[j]看作一個二進(jìn)制的01字符串P。那么咱們把S[0]~S[j-1]插入到一棵Trie樹里面，然后開始走。如果當(dāng)前P[k]=0，那么咱們肯定貪心地走Trie樹為1的邊（如果該邊指向的兒子非空）如果當(dāng)前P[k]=1，那么咱們肯定貪心地走Trie樹為0的邊（如果該邊指向的兒子非空）設(shè)最大的數(shù)有k位，那么每一次查詢的復(fù)雜度就是O(k)，查詢到S[j]的最大xor值后，把S[j]的二進(jìn)制插入到Trie里面，然后再去求S[j+1]的。總的復(fù)雜度是O(nk)，設(shè)最大的數(shù)為max，顯然就是O(nlogmax)但是上面的做法只能夠求[1,n]的，不能夠求區(qū)間[i,j]的，因為這樣子又需要重新處理以i為起點(diǎn)的前綴xor，復(fù)雜度是O(n^2logMax)一次，總的復(fù)雜度就是O(n^2MlogMax)，n^2m就爆了，logMax可以取幾十，肯定T了。這樣子好像沒有什么好的做法了…考慮這里之所以不能使用Trie樹做的原因，正是因為對于區(qū)間[i,j]的時候，不能作為答案的[1,i-1]的前綴和字符串也加進(jìn)來了?？紤]這樣一個方法，咱們假設(shè)同時擁有插入了前i-1個字符串的Trie樹，和插入前j個字符串的Trie樹，咱們可以通過比對兩個Trie樹的不同從而得到區(qū)間[i,j]的Trie樹。然后在區(qū)間[i,j]里面咱們又可以用剛才這種方法來做了可是這里的前提是咱們能同時擁有插入前i-1個字符的Trie樹和前j的字符的Trie樹…也就是所謂的歷史版本的Trie樹。而這個，就要提到Trie樹的可持久化數(shù)據(jù)結(jié)構(gòu)的可持久化簡單意義上講就是能夠保留歷史版本的數(shù)據(jù)結(jié)構(gòu)。也就是說，對于數(shù)據(jù)結(jié)構(gòu)的每一次有修改的操作，原來的數(shù)據(jù)結(jié)構(gòu)則是直接修改了做，而對于可持久化的數(shù)據(jù)結(jié)構(gòu)，它是不能修改的，它的處理辦法就是新建節(jié)點(diǎn)來存儲修改后的數(shù)據(jù)結(jié)構(gòu)。這樣子，咱們就同時擁有修改前和修改后的版本，就可以查詢歷史某一次修改時候的信息了。比如線段樹的可持久化就是一個經(jīng)典的栗子?？紤]一棵線段樹。它的區(qū)間是[1,4]，現(xiàn)在考慮在[1,3]區(qū)間插入線段，按照原來的線段樹的做法，是這樣的。這里把兩個區(qū)間的未覆蓋的狀態(tài)修改成已經(jīng)覆蓋。這里的修改操作就是直接在原數(shù)據(jù)結(jié)構(gòu)修改。而可持久化的線段樹則是不能在原節(jié)點(diǎn)修改。那怎么做？可以這樣子做，把原來的線段樹復(fù)制一份，然后在新的線段樹里面做好修改操作。這樣子咱們就同時擁有修改前和修改后的線段樹了，然后記錄下每棵線段樹代表的時間段，然后就可以按時間查找了。嗯！咱們已經(jīng)實現(xiàn)了數(shù)據(jù)結(jié)構(gòu)的可持久化，但是…時間復(fù)雜度？空間復(fù)雜度？這樣做好像就是暴力…但是好像沒有其他的做法了…考慮剛才這種做法，是為什么復(fù)雜度高？實際上沒必要復(fù)制所有的節(jié)點(diǎn)…每一次牽涉到的區(qū)間以外的節(jié)點(diǎn)再復(fù)制一次完全是浪費(fèi)時間和空間。咱們對于沒有牽涉到的節(jié)點(diǎn)都不復(fù)制，還是使用修改前的節(jié)點(diǎn)。也就是說這樣子做。這樣子做的話就可以節(jié)省空間和時間，而且咱們以前也記得，線段樹分解區(qū)間涉及到的區(qū)間是O(logN)的，所以需要建立的節(jié)點(diǎn)個數(shù)也是O(logN)的，而建立一個節(jié)點(diǎn)需要O(1)時間即可，則一次的復(fù)雜度就是O(logN)的。而空間復(fù)雜度，假設(shè)進(jìn)行了Q次修改，則復(fù)雜度就是O(N+QlogN)，而假設(shè)再利用Trie樹的動態(tài)開節(jié)點(diǎn)的思想，就可以把空間復(fù)雜度變作O(QlogN)這就是線段樹的可持久化，而這種線段樹就叫作可持久化線段樹。以前提到過的主席樹實際上是權(quán)值線段樹的可持久化而Trie樹也可以類似線段樹進(jìn)行可持久化。實際上復(fù)雜度是O(logMax)一次，時間和空間復(fù)雜度是O(nlogMax)，可以承受。這樣子咱們可以類似線段樹一樣得到所有歷史版本的Trie樹，然后對于區(qū)間詢問[i,j]，咱們fork:=i+1tojdo，找到i-1的trie樹和k-1的trie樹，使用這兩個trie樹就可以得到[i,k-1]區(qū)間的trie樹，然后類似的做就可以了。復(fù)雜度是O(NMlogMax)，NM=7.2*10^8.看似可以承受…但是logMax可以達(dá)到幾十…所以最后還是T…也就是說可持久化之后還不是正解？這簡直在逗人？咱們還能夠更快…考慮分塊…分塊大法好咱們將原來的n個數(shù)分成p塊，設(shè)f[i][j]表示以第i塊的開端為起點(diǎn)，后面j個點(diǎn)的區(qū)間的最大xor和。這個可以遞推:f[i][j]=max(f[i][j-1],[i,j-1]區(qū)間以j-1為結(jié)尾的字符串的xor和中xora[j]最大的)而后面實際上就是s[i]xors[j-1]xora[j]最大，而i未知。這個在可持久化Trie里面找i-1和j-1的Trie樹即可。復(fù)雜度是O(N*p*logMax)對于一個詢問[l,r]，咱們找出l在第i塊，則答案有可能是只在第i塊里面，不在第i塊里面，部分在第i塊。對于第一種，發(fā)現(xiàn)塊的大小只有O(N/p)，咱們直接暴力用可持久化Trie就可以做到O(N/plogMax)而對于第二種，咱們直接讀答案f[i+1][]就可以了對于第三種，咱們暴力枚舉第i塊的l后的后綴，然后在第i+1塊開端到r的可持久化Trie做就可以了。復(fù)雜度O(N/p)可以取p=sqrt(N)，則預(yù)處理復(fù)雜度是O(Nsqrt(N)logMax)而詢問復(fù)雜度就是O(Msqrt(N)logMax)，可以過極限數(shù)據(jù)了。常數(shù)較大，注意優(yōu)化Trie樹相信各位理解得很深了…接下來考慮AC自動機(jī)。實際上AC自動機(jī)就是在Trie樹的基礎(chǔ)上來的…AC自動機(jī)是做以下問題的：給你一堆字符串P[i]，和一個字符串S，求P[i]在S中出現(xiàn)了多少次。實際上就是Kmp的升級版本。假設(shè)有N個字符串P[i]，設(shè)S長度為m,按照Kmp的做法一個個做O(Nm)…看著都覺得不爽…而AC自動機(jī)實際上本身就是一棵Trie樹，然后類似Kmp的next[]數(shù)組，每一個節(jié)點(diǎn)都有一個fail指針，它的含義是當(dāng)前節(jié)點(diǎn)所代表的后綴中，能夠匹配所有字符串的任意一個的前綴的最大長度。然后求法和next[]類似…失配之后，也是沿著fail往后走…一直走到一個點(diǎn)它有匹配的邊，或者最后走到了起點(diǎn)。其實學(xué)會了Kmp的話,fail指針的做法是一樣的。這里的先將所有的字符串插入到一棵Trie樹，然后要將它變成AC自動機(jī)只需要加入fail指針。首先Trie樹某個節(jié)點(diǎn)的深度就是它所代表的字符串的長度，而fail指針指向的必定是深度遞減的點(diǎn)。為了保證求某個節(jié)點(diǎn)i的fail的時候，它的前繼節(jié)點(diǎn)fail[j]的fail指針存在，咱們必須使用bfs來求fail指針。從根節(jié)點(diǎn)bfs,所有和根節(jié)點(diǎn)相連的節(jié)點(diǎn)的fail指針初始化為根節(jié)點(diǎn)。然后其余的類似kmp的做。咱們到某一個節(jié)點(diǎn)i,枚舉它能走到的下一個節(jié)點(diǎn)j,然后對于j咱們走fail[i],直到相應(yīng)的字符也能走到一個節(jié)點(diǎn)k，那么fail[j]=k，然后把j加入bfs隊列即可。復(fù)雜度證明？考慮樹的每一條路徑，都可以看做一個序列的Kmp匹配（因為深度減少），所以復(fù)雜度也是線性的。而咱們其實可以進(jìn)一步優(yōu)化，咱們給每一個節(jié)點(diǎn)配一個go[i]數(shù)組，表示輸入字符i以后將走到哪個節(jié)點(diǎn)，這個可以在bfs的時候一起做，而求出來之后每一次只需要O(1)轉(zhuǎn)移了。雖然是常數(shù)級別優(yōu)化但是有時候很有用。而關(guān)于匹配，也是類似Kmp的做法，如果某個地方失配，則從那個地方往回跳，直到能夠匹配或者到達(dá)根節(jié)點(diǎn)。容易知道復(fù)雜度也是線性的。接下來看幾個問題.Poj2778DNASequence給出M（M<=10）個長度不超過10的字符串，問長度為N的不含這些串的字符串的個數(shù)mod100000的個數(shù)原題最多只有4個字符（A,T,C,G）N<=2000000000（9個0）肯定不能暴力枚舉串，然后對每一個串都Kmp一