国家集训队作业solution

1、L-Gap substring 解题市复旦大学附属中学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.输入数据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、输出数据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题目来源UVA 10829 L-Gap Substring中文大意如图图1所示，每组测试数据给定一个整数 以及一个长度不超过 50 000，求出满足“中间的字符串长度为 ，两端的字符串”相等这样的子串个数。题目保证 10

4、。22解题2解题为了描述方便，这里作出一些简单的约定：可以称为序列 。那么原题就转换成了求新序列 中满足形式类似与 的子序列的个数，并且| 给定。这里介绍两者此题的解题方法：解法一乍看之下本题似乎难以解决，解决这个问题。通过一些简单的思考，一步一步得来图 2: PQP 的示意图第一反应就是首先枚举 Q 的位置，然后再枚看到这个形式举 P 的长度，然后检查然后检查对应位置是否匹配。不过使用枚举法进行匹配非常浪费时间， 可以先使用后缀数组进行预处理以节省时间，不过即使这样，由于 需要枚举 Q 的位置与 P 的长度，最后的时间复杂度仍然不太理想，为(2)，显然无法通过本题。无论怎么想，方法。对于这种

5、都难以优化这两重枚举，性序列上的组合计数问题，不得不另寻更为巧妙的很容易想到一个工具：分治！。分治算法在形如快速排序等地方能顺利优化算法，尝试将其运用至本题中。不妨设过程 F(Left,Right) 可以统计在区间 Left,Right 中满足条件的子序列的个数。设 Mid 为区间 Left,Right 的中点由于分治执行，我们不需要统计那些属于 Left,Mid,Mid+1,Right 中的子序列，剩下的分两种情况。1. 点 Mid 。这种情况由于 |Q| 非常小，可以直接枚举 Q 的位置，然后直接使用之前的后缀数组配合枚举的算法解决这个问题，此32.2解法二2解题时算法多了一个系数M，不过

6、整体仍然可以在( log ) 的复杂度内完成。2.点Mid ，这种情况就比较麻烦了，可以表示成如下示意图：图 3: 情况 2由于 Mid 的存在，2 被分割成了 3 份，由于 1 = 2，把 1 也分割成 3 份，经过仔细观察，发现只需要枚举红线的位置即可解决此部分的统计问题。黄色部分的最大匹配值可以通过将整个 Mid 左面的部分倒置后求 LCP。而 Mid 以及绿色部分的匹配值可以直接通过后缀数组配合 RMQ 求的。知道了绿色与黄色部分的最大值后，那么 Q 的位置个数也可以相应得出，问题得到解决，此部分复杂度为( log )。经过层层发掘，最终得到了一个复杂度为( log )，为一个非常优秀

7、的算法。由于后缀数组配合 RMQ 代码较长，在标程中我使用了扩展 KMP 算法来代替后缀数组实现，而扩展 KMP 时间复杂度为 ()，不影响整体复杂度。解法二这个算法的基本就是利用 = ( log ) 这个表达式而=1使算法在总时间( log ) 内完成本题。的做法其实也不难想到了。首先枚举段 P可以将这个字符串每隔长度L 分段，恰好分为有了这个想法，那么的长度L，得知长度后，段，观察每段的端点，不难发现，任意一个段 P 长度为 L 的满足条件的字串必然经过两个所分的端点，如图4所示。为了避免重复，只考虑 1落在端点的情况。对于一个端点 Si，计算出他和 Si+L+Gap 的最长公共前缀与最长

8、公共后缀（可以通过后缀数组将字符串倒置后求出）之和，减去枚举的L，就是1 落在这个端点的可能字串的个数。44代码图 4: 解法二3总结最终，得到了两个思路互不相同的解法。两种解法代码复杂度没有明显的区别 (解法 1 的细节考虑略麻烦些），了选手对字符串处理工具的使用，分治以及一定的数学要求，不失为一道好题。本人最终的代码实现中，我使用了解法一。由于题目所求的最长公共前缀较为特殊，我使用了扩展KMP 算法来代替标准的后缀数组+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