國(guó)家集訓(xùn)隊(duì)作業(yè)solution

1、L-Gap substring 解題市復(fù)旦大學(xué)附屬中學(xué)April 2, 20111題目描述題目大意If a string ishe form UVU, where U is not empty, and V has exactly Lcharacters, we say UVU is an L-Gap string. For exle, abcbabc is a 1-Gap string.xyxyxyxyxy is bo2-Gap string and also a 6-Gap string, but not a 10-Gap string(because U is non-empty).Gi

2、ven a string s, and aitiveeger g, you are to nd the number of g-Gapsubstrings in s. s contains lower-case letters only, and has at most 50,000 characters.輸入數(shù)據(jù)The rst line contains a singleeger t(1 10), the number of test cases. Each of the t followings contains aneger g(1 10) followed by a string s.

3、輸出數(shù)據(jù)For each test case, prthe case number and the number of g-Gap substrings.Look at the output for sle input for details.樣例輸入211.51樣例輸出題目描述圖 1: Sle1 bbaabaaaaa5 abxxab樣例輸出Case 1: 7Case 2: 1題目來(lái)源UVA 10829 L-Gap Substring中文大意如圖圖1所示，每組測(cè)試數(shù)據(jù)給定一個(gè)整數(shù) 以及一個(gè)長(zhǎng)度不超過(guò) 50 000，求出滿足“中間的字符串長(zhǎng)度為 ，兩端的字符串”相等這樣的子串個(gè)數(shù)。題目保證 10

4、。22解題2解題為了描述方便，這里作出一些簡(jiǎn)單的約定：可以稱(chēng)為序列 。那么原題就轉(zhuǎn)換成了求新序列 中滿足形式類(lèi)似與 的子序列的個(gè)數(shù)，并且| 給定。這里介紹兩者此題的解題方法：解法一乍看之下本題似乎難以解決，解決這個(gè)問(wèn)題。通過(guò)一些簡(jiǎn)單的思考，一步一步得來(lái)圖 2: PQP 的示意圖第一反應(yīng)就是首先枚舉 Q 的位置，然后再枚看到這個(gè)形式舉 P 的長(zhǎng)度，然后檢查然后檢查對(duì)應(yīng)位置是否匹配。不過(guò)使用枚舉法進(jìn)行匹配非常浪費(fèi)時(shí)間， 可以先使用后綴數(shù)組進(jìn)行預(yù)處理以節(jié)省時(shí)間，不過(guò)即使這樣，由于 需要枚舉 Q 的位置與 P 的長(zhǎng)度，最后的時(shí)間復(fù)雜度仍然不太理想，為(2)，顯然無(wú)法通過(guò)本題。無(wú)論怎么想，方法。對(duì)于這種

5、都難以?xún)?yōu)化這兩重枚舉，性序列上的組合計(jì)數(shù)問(wèn)題，不得不另尋更為巧妙的很容易想到一個(gè)工具：分治！。分治算法在形如快速排序等地方能順利優(yōu)化算法，嘗試將其運(yùn)用至本題中。不妨設(shè)過(guò)程 F(Left,Right) 可以統(tǒng)計(jì)在區(qū)間 Left,Right 中滿足條件的子序列的個(gè)數(shù)。設(shè) Mid 為區(qū)間 Left,Right 的中點(diǎn)由于分治執(zhí)行，我們不需要統(tǒng)計(jì)那些屬于 Left,Mid,Mid+1,Right 中的子序列，剩下的分兩種情況。1. 點(diǎn) Mid 。這種情況由于 |Q| 非常小，可以直接枚舉 Q 的位置，然后直接使用之前的后綴數(shù)組配合枚舉的算法解決這個(gè)問(wèn)題，此32.2解法二2解題時(shí)算法多了一個(gè)系數(shù)M，不過(guò)

6、整體仍然可以在( log ) 的復(fù)雜度內(nèi)完成。2.點(diǎn)Mid ，這種情況就比較麻煩了，可以表示成如下示意圖：圖 3: 情況 2由于 Mid 的存在，2 被分割成了 3 份，由于 1 = 2，把 1 也分割成 3 份，經(jīng)過(guò)仔細(xì)觀察，發(fā)現(xiàn)只需要枚舉紅線的位置即可解決此部分的統(tǒng)計(jì)問(wèn)題。黃色部分的最大匹配值可以通過(guò)將整個(gè) Mid 左面的部分倒置后求 LCP。而 Mid 以及綠色部分的匹配值可以直接通過(guò)后綴數(shù)組配合 RMQ 求的。知道了綠色與黃色部分的最大值后，那么 Q 的位置個(gè)數(shù)也可以相應(yīng)得出，問(wèn)題得到解決，此部分復(fù)雜度為( log )。經(jīng)過(guò)層層發(fā)掘，最終得到了一個(gè)復(fù)雜度為( log )，為一個(gè)非常優(yōu)秀

7、的算法。由于后綴數(shù)組配合 RMQ 代碼較長(zhǎng)，在標(biāo)程中我使用了擴(kuò)展 KMP 算法來(lái)代替后綴數(shù)組實(shí)現(xiàn)，而擴(kuò)展 KMP 時(shí)間復(fù)雜度為 ()，不影響整體復(fù)雜度。解法二這個(gè)算法的基本就是利用 = ( log ) 這個(gè)表達(dá)式而=1使算法在總時(shí)間( log ) 內(nèi)完成本題。的做法其實(shí)也不難想到了。首先枚舉段 P可以將這個(gè)字符串每隔長(zhǎng)度L 分段，恰好分為有了這個(gè)想法，那么的長(zhǎng)度L，得知長(zhǎng)度后，段，觀察每段的端點(diǎn)，不難發(fā)現(xiàn)，任意一個(gè)段 P 長(zhǎng)度為 L 的滿足條件的字串必然經(jīng)過(guò)兩個(gè)所分的端點(diǎn)，如圖4所示。為了避免重復(fù)，只考慮 1落在端點(diǎn)的情況。對(duì)于一個(gè)端點(diǎn) Si，計(jì)算出他和 Si+L+Gap 的最長(zhǎng)公共前綴與最長(zhǎng)

8、公共后綴（可以通過(guò)后綴數(shù)組將字符串倒置后求出）之和，減去枚舉的L，就是1 落在這個(gè)端點(diǎn)的可能字串的個(gè)數(shù)。44代碼圖 4: 解法二3總結(jié)最終，得到了兩個(gè)思路互不相同的解法。兩種解法代碼復(fù)雜度沒(méi)有明顯的區(qū)別 (解法 1 的細(xì)節(jié)考慮略麻煩些），了選手對(duì)字符串處理工具的使用，分治以及一定的數(shù)學(xué)要求，不失為一道好題。本人最終的代碼實(shí)現(xiàn)中，我使用了解法一。由于題目所求的最長(zhǎng)公共前綴較為特殊，我使用了擴(kuò)展KMP 算法來(lái)代替標(biāo)準(zhǔn)的后綴數(shù)組+RMQ，一定程度上減少了代碼量。4代碼12345678910111213141516$M 1000000usesMath;constMaxN = 50000+10;type

9、TAns = array 1.MaxN of Long;varStr,StrF,LStr,RStr,LStrF,SS: Ansistring; Ans,Ans1,Prev,Next: TAns;N,Gap: Longch: Char;54代碼17procedure KMP(var Mode,Goal: Ansistring;var Prev,Ans:TAns;Start:);1819202122232425262728293031323334353637383940414243444546474849505152vari,j,k: Long;beginif Start thenAns1:=Le

10、ngth(Mode); j:=0;for i:=Ord(Start)+1 to Length(Goal) do beginwhile (j0) and (GoaliModej+1) do beginAnsi-j:=j;for k:=i-j+1 to i-Nextj-1 doAnsk:=Prevk-i+j+1; j:=Nextj;end;if Goali=Modej+1 then Inc(j);end;end;procedure KMP_EXT(var Mode,Goal: Ansistring;varvarAns: TAns);i,j: Longbegin;Mode:=Mode+$; Goal

11、:=Goal+#;Fillchar(Next,Length(Mode)*4,0); Fillchar(Prev,Length(Mode)*4,0); j:=0;for i:=2 to Length(Mode) do beginwhile (j0) and (ModeiModej+1) doj:=Nextj;if Modei=Modej+1 then Inc(j);64代碼53545556575859606162636465Nexti:=j;end; Fillchar(Ans,Length(Goal)*4,0); if ModeGoal thenbeginKMP(Mode,Mode,Prev,P

12、rev,True); KMP(Mode,Goal,Prev,Ans,False);end elseKMP(Mode,Mode,Ans,Ans,True);end;function Calc(var Str: Ansistring;Mid: Longinline;var):Long;6667686970717273747576777879808182838485868788A,B,T,i: Longbegin;LStr:=Copy(Str,1,Mid); RStr:=Copy(Str,Mid+1,Length(Str)-Mid); SetLength(LStrF,Mid);for i:=1 to

13、 Mid doLStrFi:=LStrMid-i+1; KMP_EXT(LStrF,LStrF,Ans); KMP_EXT(RStr,LStr,Ans1);Calc:=0;for i:=1 to Mid-1 do beginA:=Ans1i+1;B:=AnsMid-i+1;T:=Mid-i-Gap;Inc(Calc,Max(Min(A,T-1)-Max(T-B,1)+1,0);end;end;function Merge(L,R: Long): Longvar;i,j,L1,R1,M,Len: Long;74代碼89909192939495969798991001011021031041051

14、06107108109110111112113114115116117118119120121122123124125beginLen:=R-L+1;if Len-Gap2 then Exit(0);Merge:=0; M:=(L+R) div 2;Merge:=Merge(L,M)+Merge(M+1,R);for i:=0 to Gap do beginL1:=M-i+1;R1:=L1+Gap-1;Dec(L1);Inc(R1);if (L1R) then Continue;LStr:=Copy(SS,L,L1-L+1); RStr:=Copy(SS,R1,R-R1+1);KMP_EXT(RStr,LStr,Ans);for j:=L to L1 doif j+Ansj-L+1-1=L1 then Inc(Merge);end; Str:=Copy(SS,L,Len); M:=(Len+1) div 2; Inc(Merge,Calc(Str,M); SetLength(StrF,Len); for i:=1 to Len doStrFLen-i+1:=Stri;Inc(Merge,Calc(StrF,Len-M);end;vari,j: Longbegin;$IFDEF HOMEAssign(Input,input.txt);Rese