字符串的相關(guān)算法字符串的相關(guān)算法還是在前面的話(huà)因?yàn)楸救颂酢赃@幾天講的ppt經(jīng)常會(huì)發(fā)現(xiàn)錯(cuò)誤，建議在ppt大略的基礎(chǔ)上去找相關(guān)論文學(xué)習(xí)?？赡苤攸c(diǎn)還是在原理的簡(jiǎn)單解釋…有的地方聽(tīng)不懂的話(huà)也沒(méi)關(guān)系，因?yàn)槊總€(gè)人沒(méi)有實(shí)現(xiàn)過(guò)代碼之前實(shí)際上都是這樣的，可能會(huì)對(duì)某些地方不理解不影響你對(duì)整個(gè)算法的印象。以后如果能夠?qū)ｉT(mén)思考的話(huà)也許就會(huì)快捷許多。字符串算法有一些的原理看起來(lái)比較麻煩，但是代碼量往往特別短，所以建議要去完全理解某個(gè)算法的原理，這樣子以后就算把模板忘了，也許也能夠通過(guò)原理寫(xiě)出相應(yīng)的代碼。一開(kāi)始可以學(xué)習(xí)一下練習(xí)模板。字符串算法的模板往往很短，很容易上手。還是在前面的話(huà)因?yàn)楸救颂酢赃@幾天講的ppt經(jīng)常會(huì)發(fā)現(xiàn)錯(cuò)大前天提到了分治…提到了這樣一個(gè)方程…f(n)=f(n/2)+f(n/2)+O(1)這個(gè)咱當(dāng)時(shí)是說(shuō)f(n)=O(nlogn)那是咱SB…TooNa?ve考慮線(xiàn)段樹(shù)的節(jié)點(diǎn)，就是這個(gè)分布的…可是線(xiàn)段樹(shù)的節(jié)點(diǎn)個(gè)數(shù)是O(n)的這個(gè)的解顯然應(yīng)該是f(n)=O(n)在此表示歉意大前天提到了分治…咱所知道的字符串算法Pascal的Pos函數(shù)…Hash哈希Kmp和擴(kuò)展KmpTrie樹(shù)AC自動(dòng)機(jī)后綴樹(shù)，后綴數(shù)組(SA)，后綴自動(dòng)機(jī)(SAM)Manacher算法亂搞最近新出來(lái)的：回文自動(dòng)機(jī)(PAM)(太弱不會(huì))。咱所知道的字符串算法Hash哈希Hash應(yīng)該都知道…常用的Hash函數(shù)?首先直接把每一個(gè)字符的ASCII值加起來(lái)作為Hash值不取模的情況很容易沖突…常用的Hash，自己設(shè)一個(gè)X進(jìn)制(X>=你的字符集的大小-1，比如大寫(xiě)字母有26個(gè)字母，字符集大小為26)然后咱們就有Hash=∑S[i]*X^(i-1)假設(shè)字符串長(zhǎng)度為s，這個(gè)就可以在O(s)的時(shí)間內(nèi)算出來(lái)。顯然如果存的下最后的Hash值的話(huà)，每一個(gè)字符串的Hash值必定不相同。Q:為什么？Hash哈希Hash應(yīng)該都知道…實(shí)際上這種計(jì)算方法，每個(gè)字符串都是X進(jìn)制下的一個(gè)數(shù)，而Hash值就是這個(gè)X進(jìn)制的數(shù)轉(zhuǎn)十進(jìn)制的值，由于X進(jìn)制的數(shù)互不相同，顯然Hash值，即十進(jìn)制的數(shù)也互不相同。Q：那如果字符串長(zhǎng)度過(guò)大，以致會(huì)爆怎么辦？取個(gè)模唄…Q：那如果兩個(gè)字符串不同Hash值取某個(gè)模最后相同怎么辦？取多個(gè)模唄…如果多個(gè)模的情況下都相同那么就是同一個(gè)字符串。Q：如果取多個(gè)模都相同呢？……首先，這個(gè)模是你自己定的，所以一般數(shù)據(jù)是沒(méi)辦法全部卡的。接著，由中國(guó)剩余定理，只要取到的每個(gè)模足夠大，那么最后也可以保證一定范圍內(nèi)的Hash值是一定的。Q：中國(guó)剩余定理是什么？以后講數(shù)學(xué)的時(shí)候會(huì)講吧…順便可以百度_(:зゝ∠)_實(shí)際上這種計(jì)算方法，每個(gè)字符串都是X進(jìn)制下的一個(gè)數(shù)，而Has除了這種Hash以外，字符串Hash也有很多其他的版本，比如ELFhash(黑書(shū)上的)據(jù)說(shuō)這個(gè)的效果比上面的還好，咱沒(méi)試過(guò)_(:зゝ∠)_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;除了這種Hash以外，字符串Hash也有很多其他的版本，比如Bzoj1014JSOI2008火星人火星人最近研究了一種操作：求一個(gè)字串兩個(gè)后綴的公共前綴。比方說(shuō)，有這樣一個(gè)字符串：madamimadam，我們將這個(gè)字符串的各個(gè)字符予以標(biāo)號(hào)：序號(hào)：1234567891011

字符madamimadam現(xiàn)在，火星人定義了一個(gè)函數(shù)LCQ(x,y)，表示：該字符串中第x個(gè)字符開(kāi)始的字串，與該字符串中第y個(gè)字符開(kāi)始的字串，兩個(gè)字串的公共前綴的長(zhǎng)度。比方說(shuō)，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函數(shù)的過(guò)程中，火星人發(fā)現(xiàn)了這樣的一個(gè)關(guān)聯(lián)：如果把該字符串的所有后綴排好序，就可以很快地求出LCQ函數(shù)的值；同樣，如果求出了LCQ函數(shù)的值，也可以很快地將該字符串的后綴排好序。盡管火星人聰明地找到了求取LCQ函數(shù)的快速算法，但不甘心認(rèn)輸?shù)牡厍蛉擞纸o火星人出了個(gè)難題：在求取LCQ函數(shù)的同時(shí)，還可以改變字符串本身。具體地說(shuō)，可以更改字符串中某一個(gè)字符的值，也可以在字符串中的某一個(gè)位置插入一個(gè)字符。地球人想考驗(yàn)一下，在如此復(fù)雜的問(wèn)題中，火星人是否還能夠做到很快地求取LCQ函數(shù)的值。字符串長(zhǎng)度始終<=10^5，操作數(shù)<=10^4Bzoj1014JSOI2008火星人火星人最近研究了一題目是什么意思？一般先化成裸題。LCP是最長(zhǎng)公共前綴，現(xiàn)給出一個(gè)字符串S，支持以下操作：1詢(xún)問(wèn)LCP(x,y)，也就是原字符串從x開(kāi)始的字符串和從y開(kāi)始的字符串最長(zhǎng)的公共前綴2修改，修改原S的一個(gè)字符3添加，在S的第X個(gè)字符后面添加一個(gè)字符。這個(gè)有什么做法？題目是什么意思？一般先化成裸題。也是可以把問(wèn)題分開(kāi)來(lái)考慮，比如，怎么快速求LCP?Hash?考慮使用Hash來(lái)做實(shí)際上這里的LCP(x,y)的x,y所代表的字符串都是S的后綴考慮每一個(gè)后綴Suffix[i]，就是從S的第i個(gè)字符開(kāi)始的后綴，它的Hash值就是Hash[i]=S[i]+S[i+1]*26+S[i+2]*26^2...然后Suffix[i]的某個(gè)前綴S[i..j]的Hash值怎么算？Hash=Hash[i]-Hash[j]*26^(j-i+1)預(yù)處理出所有后綴的Hash[i]以及26^k的話(huà)也就是說(shuō)咱們能夠O(1)地求出每一個(gè)后綴的某個(gè)前綴的Hash值。也是可以把問(wèn)題分開(kāi)來(lái)考慮，比如，怎么快速求LCP?之前又提到過(guò)一點(diǎn)：對(duì)于兩個(gè)相同的字符串，他們的Hash值相同，取模之后也相同。對(duì)于兩個(gè)不同的字符串，他們的Hash值不相同，但取模之后可能相同，模的數(shù)越大，同時(shí)取不同的模，最后相同的可能性越小。以這兩點(diǎn)作為依據(jù)，咱們可以這樣子做。對(duì)于詢(xún)問(wèn)后綴X與Y的詢(xún)問(wèn)，二分答案，即LCP的長(zhǎng)度L，然后O(1)求出這個(gè)長(zhǎng)度為L(zhǎng)的前綴的Hash值，取不同的模，如果不同的模之后都相同，則可認(rèn)為這兩個(gè)長(zhǎng)度為L(zhǎng)的字符串相同，二分答案區(qū)間上移，否則則認(rèn)為不同，二分答案區(qū)間下移。這樣做的復(fù)雜度是O(logS)一次，S為字符串的長(zhǎng)度。之前又提到過(guò)一點(diǎn)：但是對(duì)于修改操作，咱們?cè)撛趺醋?？咱們可以發(fā)現(xiàn)，修改了字符S[i]，那么受到影響的就是它前面的所有字符的Hash值，對(duì)于前面來(lái)說(shuō)這個(gè)改動(dòng)比較大…而添加字符…對(duì)于所有的Hash值，都要重算…這怎么做啊，這沒(méi)法做啊…實(shí)際上還是可以做的…咱們以原字符串的順序建立平衡樹(shù)，每個(gè)節(jié)點(diǎn)i維護(hù)一個(gè)信息，就是它為根的子樹(shù)所構(gòu)成的字符串的Hash值和它為根的子樹(shù)的大小size。但是對(duì)于修改操作，咱們?cè)撛趺醋?？那么遞推式？Hash[fa]=Hash[lson]+s[fa]*26^(Size[lson])+Hash[rson]*26^(Size[lson]+1)然后這樣子就可以做了…每一次把一個(gè)后綴全部弄到一棵子樹(shù)里面，然后它的Hash值就是根節(jié)點(diǎn)的那個(gè)Hash值。這個(gè)得用Splay來(lái)做對(duì)于修改，直接在子樹(shù)上修改，然后再往根節(jié)點(diǎn)一路走，修改沿途的節(jié)點(diǎn)的Hash值。對(duì)于添加，直接Splay添加節(jié)點(diǎn)，然后往根節(jié)點(diǎn)走，每個(gè)節(jié)點(diǎn)的size+1,Hash值也更新。Splay一次的復(fù)雜度是O(logS)，所以一次的復(fù)雜度是O(logS*logS)，假設(shè)詢(xún)問(wèn)q次，總復(fù)雜度就是O(qlogS*logS)P黨Splay比較吃力,咱blog有(別人的)AC代碼，實(shí)在A不了可以去看一看。Hash的實(shí)現(xiàn)：2行即可…(不算上預(yù)處理)那么遞推式？Hash[fa]=Hash[lson]+s[fa上面所提到的Hash能夠在O(1)的時(shí)間判斷兩個(gè)串是否相同（如果預(yù)處理相應(yīng)的Hash值）。然后Hash不僅僅只可用于字符串，還可以用于某些狀態(tài)的壓縮以及O(1)的查找。比如上一次某道求某個(gè)數(shù)全部排列模m=0的數(shù)的個(gè)數(shù)的數(shù)位dp的，咱們暴力枚舉一半的排列a，然后將另一半的排列模m的值轉(zhuǎn)Hash，然后對(duì)于排列a，可以計(jì)算出為了模m=0另一半所需要的模值，然后O(1)可處理詢(xún)問(wèn)。還比如廣搜，為了判斷某個(gè)狀態(tài)之前是否搜過(guò)，也可以設(shè)計(jì)一個(gè)函數(shù)做成Hash值。這些都是常見(jiàn)的運(yùn)用。上面所提到的Hash能夠在O(1)的時(shí)間判斷兩個(gè)串是否相同（接著提到的是字符串匹配問(wèn)題…給你一個(gè)字符串S，一個(gè)字符串P，求P在S中出現(xiàn)了幾次。S長(zhǎng)度為n，P長(zhǎng)度為m。保證m<=n咱們所知道的算法…1.暴力算法,pos()+delete()…以上是檢驗(yàn)這題是否是水題的標(biāo)準(zhǔn)2.Rabin-Karp算法。這是什么鬼？實(shí)際上就是剛才講的Hash…咱們對(duì)字符串P，可以用剛才X進(jìn)制的Hash函數(shù)，然后對(duì)于串P咱們有個(gè)Hash函數(shù)u，對(duì)于S的每個(gè)長(zhǎng)度為m的子串，計(jì)算出一個(gè)Hash函數(shù)，總共有n-m+1個(gè)Hash函數(shù)，將它們和P的Hash函數(shù)u比較即可。然后計(jì)算S的n-m+1個(gè)Hash函數(shù)可以遞推。遞推式？（假設(shè)字符集大小為x）復(fù)雜度？O(n-m+1)。（還可以推廣到二維平面的字符串匹配!!）這么好的算法，為什么咱們竟然不知道？因?yàn)檫@里的Hash是取模的，取模之后有可能相同，而咱們這里要求的算法是100%正確，也就是說(shuō)精確匹配，如果P和某個(gè)的Hash值不同顯然無(wú)視，可是如果相同的話(huà)還得從頭比較。（因?yàn)閺娜∧５腍ash值不能100%確定某個(gè)串一定等于另一個(gè)）這樣的話(huà)最壞n-m+1個(gè)都要比較，比較一次O(m),復(fù)雜度O(m(n-m+1))。這個(gè)算法最壞復(fù)雜度和暴力差不多…但是期望情況很好。接著提到的是字符串匹配問(wèn)題…3.有限狀態(tài)自動(dòng)機(jī)匹配（這個(gè)后面ppt會(huì)提到，預(yù)計(jì)下次講了）這個(gè)的復(fù)雜度，設(shè)字符集大小為∑，那么復(fù)雜度建立字符串P的自動(dòng)機(jī)O(m∑)，匹配O(n)。好處是自動(dòng)機(jī)建立好之后，可以同時(shí)求多個(gè)串S中是否出現(xiàn)P。4.Knuth-Morris-Pratt算法也就是所說(shuō)的KMP算法。1）KMP算法的原理？2）KMP算法復(fù)雜度的證明？3）能隨手敲一個(gè)KMP嗎？3.有限狀態(tài)自動(dòng)機(jī)匹配（這個(gè)后面ppt會(huì)提到，預(yù)計(jì)下次講了）KMP算法其實(shí)不難理解。設(shè)這里有個(gè)S串一部分為ababaab，P串為ababaca，匹配到第六個(gè)字符的時(shí)候失效，這個(gè)時(shí)候咱們就想盡量利用已經(jīng)匹配到的信息?？紤]暴力做法是怎么樣的。KMP算法其實(shí)不難理解。暴力的做法就是右移一位，然后再?gòu)念^比較，但是咱們通過(guò)之前的匹配知道這里是不可能有匹配的。因?yàn)橐呀?jīng)匹配的部分ababaa的babaa的這個(gè)后綴和ababaa這個(gè)的公共前綴為0.所以這里還去匹配是不理智的。字符串的有關(guān)算法講述課件咱們發(fā)現(xiàn)這里的信息所涉及的串…好像只跟P有關(guān)…而這個(gè)暴力的過(guò)程，實(shí)際上就是拿P的第i個(gè)后綴和它的前綴繼續(xù)匹配。而如果這個(gè)后綴能夠匹配P的某個(gè)前綴，那么它就能繼續(xù)在失配的那個(gè)地方匹配下去。實(shí)際上就是求P已經(jīng)匹配的串p[1..i]的最大后綴，使得它是p[1..i]的公共前綴!而這個(gè)東西是只和P字符串有關(guān)…比如ababaa字符串，它的p[1..5]的最大后綴是[3..5]也就是aba,它和ababaa的前綴p[1..3]匹配。這個(gè)時(shí)候咱們直接將P移動(dòng)到S的ababaa的第二個(gè)a處即可。這個(gè)時(shí)候已經(jīng)有3個(gè)字符被匹配了。咱們發(fā)現(xiàn)這里的信息所涉及的串…好像只跟P有關(guān)…所以咱們只要求P的每個(gè)前綴的最長(zhǎng)的相同后綴就可以了。設(shè)這個(gè)后綴的長(zhǎng)度是next[]next[i]的含義就是p[1..i]這個(gè)字符串的能夠匹配前綴的最大后綴的長(zhǎng)度。幾個(gè)小練習(xí)來(lái)理解.abbabba的next[4]=?next[6]=?next[4]=1,next[6]=3.這個(gè)next[]函數(shù)理解了之后，考慮next[next[]]的含義？所以咱們只要求P的每個(gè)前綴的最長(zhǎng)的相同后綴就可以了。next[i]是p[1..i]這個(gè)字符串能夠匹配前綴的最大后綴的長(zhǎng)度,也就是說(shuō)p[1..i]里面p[1..next[i]]=p[i-next[i]+1..i]而且這個(gè)是最長(zhǎng)的。那么next[next[i]]就是p[1..next[i]]這個(gè)字符串的能夠匹配前綴的最大后綴的長(zhǎng)度，又由于p[1..next[i]]=p[i-next[i]+1..i]，所以這個(gè)可以理解為：能夠匹配p[1..next[i]]前綴的p[i-next[i]+1..i]的最大后綴的長(zhǎng)度實(shí)際上這個(gè)又等價(jià)于匹配p[1..i]前綴的p[1..i]的第二大后綴。也就是說(shuō)next[next[i]]表示的就是能夠匹配p[1..i]的前綴的第二大后綴的長(zhǎng)度。那么next[next[next[i]]]?表示的就是能夠匹配p[1..i]的前綴的第三大后綴的長(zhǎng)度。以此類(lèi)推next[i]是p[1..i]這個(gè)字符串能夠匹配前綴的最大后現(xiàn)在考慮求next[i]，假設(shè)已經(jīng)知道next[1],next[2],next[3],…next[i-1]。因?yàn)閚ext[i-1]表示的是p[1..i-1]的匹配前綴的最長(zhǎng)后綴。那么如果p[next[i-1]+1]=p[i]的話(huà)，那么顯然p[1..i]的匹配的最長(zhǎng)前綴就是p[1..next[i-1]+1]了。這個(gè)時(shí)候next[i]=next[i-1]+1;如果p[next[i-1]+1]<>p[i]。咱們也沒(méi)關(guān)系。next[i]表示的是p[1..i-1]匹配前綴的最長(zhǎng)后綴，咱們可以繼續(xù)去找第二長(zhǎng)，第三長(zhǎng)后綴…繼續(xù)去匹配。怎么做？之前提到了，假設(shè)第K長(zhǎng)的后綴的長(zhǎng)度是u，那么第K+1長(zhǎng)的后綴的長(zhǎng)度就是next[u]枚舉第K長(zhǎng)后綴，判斷其對(duì)應(yīng)前綴+1的字符是不是s[i]，如果是的話(huà)，這個(gè)就是p[1..i]的匹配的最長(zhǎng)前綴了?，F(xiàn)在考慮求next[i]，假設(shè)已經(jīng)知道next[1],nex某個(gè)實(shí)現(xiàn)代碼如下：next[1]:=1;Fori:=2tomdoBeginj:=next[i-1];{其實(shí)不需要寫(xiě)這句話(huà)，因?yàn)檫@個(gè)過(guò)程倒數(shù)第二行已經(jīng)有了這句話(huà)，這里標(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； 代碼量也是極短的…某個(gè)實(shí)現(xiàn)代碼如下：以上是預(yù)處理。接下來(lái)是KMP算法的匹配。實(shí)際上比預(yù)處理簡(jiǎn)單多了。假設(shè)匹配兩個(gè)字符，匹配得上，兩個(gè)都+1，這個(gè)顯然?？紤]匹配不上，假設(shè)這個(gè)時(shí)候是p[1..i]已經(jīng)匹配,p[i+1]和s[x]失配，咱們只需要沿著next[i]走，然后繼續(xù)匹配即可，如果走到0了還是沒(méi)能匹配，那么s[x]無(wú)論如何都匹配不了，接下來(lái)繼續(xù)匹配s[x+1]和p[1]?？紤]P：abbabbaS：aaababbababbabbaba的匹配過(guò)程。以上是預(yù)處理。接下來(lái)是KMP算法的匹配。實(shí)際上比預(yù)處理簡(jiǎn)單多最后就是復(fù)雜度證明了…先證明預(yù)處理的復(fù)雜度是線(xiàn)性的，也就是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減少肯定不超過(guò)m，考慮最壞情況j每次只減少1，那么最后也只減少m次，所以復(fù)雜度是O(m)線(xiàn)性的。最后就是復(fù)雜度證明了…Smartojp1848統(tǒng)計(jì)單詞數(shù)

一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)?，F(xiàn)在，請(qǐng)你編程實(shí)現(xiàn)這一功能，具體要求是：給定一個(gè)單詞，請(qǐng)你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。!!注意：匹配單詞時(shí)，不區(qū)分大小寫(xiě)，但要求完全匹配，即給定單詞必須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫(xiě)的情況下完全相同（參見(jiàn)樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見(jiàn)樣例2）。輸出單詞出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置(-1代表未出現(xiàn))單詞的位置從0開(kāi)始Smartojp1848統(tǒng)計(jì)單詞數(shù)

一般的文本編輯器都有ToTotobeornottobeisaquestion20(出現(xiàn)2次，第一次出現(xiàn)在0處）toDidtheOttomanEmpireloseitspoweratthattime-1單詞長(zhǎng)度<=10文章長(zhǎng)度<=10^6To這道題不像普通的匹配，必須要求原文章的對(duì)應(yīng)字符是一個(gè)獨(dú)立的單詞。然而這并沒(méi)有什么…因?yàn)樵蹅兛梢哉页鲆粋€(gè)單詞在原文章出現(xiàn)的所有位置，所以只需要每找到一個(gè)，判斷他是否是一個(gè)獨(dú)立的單詞就可以了。判斷是否是獨(dú)立的單詞，其實(shí)就是看這個(gè)字符串前面和后面是否是空格就可以了…一個(gè)獨(dú)立的單詞按照題目意思，必然是前后都是空格…問(wèn)題解決。這道題不像普通的匹配，必須要求原文章的對(duì)應(yīng)字符是一個(gè)獨(dú)立的單CHHSYOI2015Round2

E.字符串與KMP給你一個(gè)n<=10^6的字符串，求該字符串的最小循環(huán)節(jié)。循環(huán)節(jié)就是該字符串可由該循環(huán)節(jié)重復(fù)得到。比如abcabc的最小循環(huán)節(jié)是3，aaaaa的最小循環(huán)節(jié)是1.要做這道題請(qǐng)加入CH上華師一附中的小組，無(wú)需審核。CHHSYOI2015Round2

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

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

Smartojp2168

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

AnnandHalf-Palindrome

簡(jiǎn)要翻譯：定義半回文串S，長(zhǎng)度為n,就是滿(mǎn)足以下條件的字符：對(duì)于所有滿(mǎn)足以下條件的第i位：1）i為奇數(shù)2）i<=(n+1)/23）有S[i]=S[n-i+1]。那么則稱(chēng)該字符串S為半回文串?，F(xiàn)給出一個(gè)長(zhǎng)度為N的字符串S，S的所有子串中是半回文串的按字典序從小到大排成一列，求出第K小的半回文串。這里的字符只有a,b兩個(gè)N<=5000CFRound#311div2E

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