{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { max-width: 100%; }\r\n .fontweight {\r\n font-weight: bold;\r\n }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。\u003c/p\u003e \n \u003cp\u003e小Hi发现旋律可以循环,每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”,还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。\u003c/p\u003e \n \u003cp\u003e小Hi对此产生了浓厚的兴趣,他有若干段旋律,和一部音乐作品。对于每一段旋律,他想知道有多少在音乐作品中的子串(重复便多次计)和该旋律是“循环相似旋律”。\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e解题方法提示\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e解题方法提示\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:我们已经对后缀自动机比较熟悉了,今天我们再来道稍有难度的题。\u003c/p\u003e \n \u003cp\u003e小Ho:好!这道题目让我们求的是若干串在另一个长串S中各自作为子串出现的次数,只是匹配的方式从完全相等变成了“循环同构”。\u003c/p\u003e \n \u003cp\u003e小Hi:没错!如果匹配方式是完全相等的话,本题就可以使用AC自动机或者\u003ca href\u003d\"https://hihocoder.com/problemset/problem/1036\"\u003etrie图\u003c/a\u003e完美的解决。\u003c/p\u003e \n \u003cp\u003e小Ho:既然这个问题也和子串有关系,那么不妨试试后缀自动机。\u003c/p\u003e \n \u003cp\u003e小Hi:对。和上一期一样,你可以先想想如果询问只有一个串T应该怎么做。\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,那自然就考虑所有T的循环同构的串在长串S中出现的次数。\u003c/p\u003e \n \u003cp\u003e小Hi:没错。循环同构有点麻烦,如果我们枚举与T循环同构的串,再依次判断是否在S中出现过。那复杂度至少是O(length(T)^2)的了。\u003c/p\u003e \n \u003cp\u003e小Ho:恩。比如T\u003d\"abcd\"的话,我们要判断4个串\"abcd\", \"bcda\", \"cdab\", \"dabc\"在S中出现的次数。\u003c/p\u003e \n \u003cp\u003e小Hi:为了能顺利解决循环同构的问题。我们要做点准备,先考虑这么一个问题。\u003cspan class\u003d\"fontweight\"\u003e对于给定的字符串S和T,求S和T的最长公共子串\u003c/span\u003e。小Ho,你知道最长公共子串是什么吧? 要注意子串和子序列不同哦。\u003c/p\u003e \n \u003cp\u003e小Ho:知道。比如\"aabbabd\"和\"abbabb\"的最长公共子串就是\"abbab\"。\u003c/p\u003e \n \u003cp\u003e小Hi:我们利用SAM,可以做到对于T的每个位置i,都能求出以T[i]结尾的最长公共子串是什么。以你上面说的\"aabbabd\"和\"abbabb\"为例。我们可以求出\u003c/p\u003e \n \u003cpre\u003eS: aabbabd\r\nT: abbabb \r\n1:a\r\n2: ab\r\n3: abb\r\n4: abba\r\n5: abbab\r\n6: abb\u003c/pre\u003e \n \u003cp\u003e小Ho:这个怎么求呢?\u003c/p\u003e \n \u003cp\u003e小Hi:我们先构造S的后缀自动机。然后对于每个结束位置T[i],维护两个变量。一个是当前状态u,表示T[i]结尾的最长公共子串在S的SAM的哪个状态里;二是当前匹配长度l,表示T[i]结尾的最长公共子串的长度。初始时u\u003d初始状态S,l\u003d0。 \u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/f091cd6fecd83d6aecc52ab641a4933f?v\u003d1659761399\" title\u003d\"week131.png\"\u003e \n \u003cp\u003e小Hi:假设我们已经知道T[i-1]对应的(u, l),要求T[i]对应的(u\u0027, l\u0027)。如果trans[u][T[i]]存在的话,那么直接令u\u0027\u003dtrans[u][T[i]], l\u0027 \u003d l+1即可。\u003c/p\u003e \n \u003ctable class\u003d\"table table-bordered table-hover\" style\u003d\"width:70%;\"\u003e \n \u003cthead\u003e \n \u003ctr\u003e \n \u003cth\u003e位置\u003c/th\u003e \n \u003cth\u003eu\u003c/th\u003e \n \u003cth\u003el\u003c/th\u003e \n \u003c/tr\u003e \n \u003c/thead\u003e \n \u003ctbody\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[0]\u003c/td\u003e \n \u003ctd\u003eS\u003c/td\u003e \n \u003ctd\u003el\u003d0\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[1]\u003c/td\u003e \n \u003ctd\u003etrans[S][a]\u003d1\u003c/td\u003e \n \u003ctd\u003e1\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[2]\u003c/td\u003e \n \u003ctd\u003etrans[1][b]\u003d8\u003c/td\u003e \n \u003ctd\u003e2\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[3]\u003c/td\u003e \n \u003ctd\u003etrans[8][b]\u003d4\u003c/td\u003e \n \u003ctd\u003e3\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[4]\u003c/td\u003e \n \u003ctd\u003etrans[4][a]\u003d6\u003c/td\u003e \n \u003ctd\u003e4\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[5]\u003c/td\u003e \n \u003ctd\u003etrans[6][b]\u003d7\u003c/td\u003e \n \u003ctd\u003e5\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[6]\u003c/td\u003e \n \u003ctd\u003etrans[7][b]\u003dNULL\u003c/td\u003e \n \u003ctd\u003e?\u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e \n \u003c/table\u003e \n \u003cp\u003e小Ho:那如果遇到trans[u][T[i]]不存在怎么办? 比如处理的T[6]的时候,trans[7][b]不存在。\u003c/p\u003e \n \u003cp\u003e小Hi:这时我们要沿suffix-path(u-\u0026gt;S)找到一个状态v满足trans[v][T[i]]存在。所以先找suffix[7]\u003d8,而trans[8][b]\u003d4存在。这时令u\u003dtrans[v][T[i]], l\u003dmaxlen(v)+1。\u003c/p\u003e \n \u003ctable class\u003d\"table table-bordered table-hover\" style\u003d\"width:70%;\"\u003e \n \u003cthead\u003e \n \u003ctr\u003e \n \u003cth\u003e位置\u003c/th\u003e \n \u003cth\u003eu\u003c/th\u003e \n \u003cth\u003el\u003c/th\u003e \n \u003c/tr\u003e \n \u003c/thead\u003e \n \u003ctbody\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[0]\u003c/td\u003e \n \u003ctd\u003eS\u003c/td\u003e \n \u003ctd\u003el\u003d0\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[1]\u003c/td\u003e \n \u003ctd\u003etrans[S][a]\u003d1\u003c/td\u003e \n \u003ctd\u003e1\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[2]\u003c/td\u003e \n \u003ctd\u003etrans[1][b]\u003d8\u003c/td\u003e \n \u003ctd\u003e2\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[3]\u003c/td\u003e \n \u003ctd\u003etrans[8][b]\u003d4\u003c/td\u003e \n \u003ctd\u003e3\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[4]\u003c/td\u003e \n \u003ctd\u003etrans[4][a]\u003d6\u003c/td\u003e \n \u003ctd\u003e4\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[5]\u003c/td\u003e \n \u003ctd\u003etrans[6][b]\u003d7\u003c/td\u003e \n \u003ctd\u003e5\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[6]\u003c/td\u003e \n \u003ctd\u003etrans[7][b]\u003dNULL\u003c/td\u003e \n \u003ctd\u003e?\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[6]\u003c/td\u003e \n \u003ctd\u003etrans[suffix[7]][b]\u003dtrans[8][b]\u003d4\u003c/td\u003e \n \u003ctd\u003emaxlen[8]+1\u003d3\u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e \n \u003c/table\u003e \n \u003cp\u003e小Ho:这里trans[u][T[i]]不存在就沿着suffix-path(u-\u0026gt;S)向前找的过程好像类似\u003ca href\u003d\"https://hihocoder.com/problemset/problem/1015\"\u003eKMP\u003c/a\u003e中当前字符失配就沿next数组向前找? \u003c/p\u003e \n \u003cp\u003e小Hi:没错,过程是类似的。都是在\"abbab\"+\u0027b\u0027失配时,试图找到\"abbab\"的一个最长后缀s使得s+\u0027b\u0027不失配。我们知道\"abbab\"的后缀都在suffix-path(u-\u0026gt;S)里,所以沿着suffix-path(u-\u0026gt;S)向前找即可。\u003c/p\u003e \n \u003cp\u003e小Ho:如果最后直到初始状态S都没有trans[v][T[i]]存在呢?\u003c/p\u003e \n \u003cp\u003e小Hi:如果trans[S][T[i]]不存在,那字符T[i]肯定是没在字符串S中出现过。这时我们令u\u003dS, l\u003d0从T[i+1]重新开始即可。\u003c/p\u003e \n \u003cp\u003e小Hi:好了,现在对于T的每个位置i,我们都能求出以T[i]结尾的最长公共子串是什么。(严格来说我们知道最长公共子串的长度l)那我们能知道这个最长公共子串在S中出现了多少次么?\u003c/p\u003e \n \u003cp\u003e小Ho:这个我知道。我们既然已经知道子串对应的状态u,那么|endpos(u)|就是子串出现的次数。这个问题我们已经在\u003ca href\u003d\"https://hihocoder.com/problemset/problem/1449\"\u003ehiho一下 第129周\u003c/a\u003e学习过了。\u003c/p\u003e \n \u003cp\u003e小Hi:现在我们的准备工作做完了。小Ho你先回顾一下前面的内容,下面我们要开始解决这周的问题了。\u003c/p\u003e \n \u003cp\u003e小Ho:好的。\u003c/p\u003e \n \u003cp\u003e小Hi:现在我们要处理T的循环同构串们。这里有一个常用的技巧,假设T的长度是n,我们令T\u0027\u003dT + T[1..n-1]形成一个新的串T\u0027。例如对于\"abcd\",我们把\"abc\"拼在\"abcd\"后面,得到新的T\u003d\"abcdabc\"。这样\"abcd\"的循环同构串就变成了T\u0027\u003d\"abcdabc\"的长度为n的子串。 \u003c/p\u003e \n \u003cp\u003e小Ho:哦!然后我们再用之前讲的方法求出在每个位置T\u0027[i]结束的最长公共子串。我们可以求出对应的(u, l),如果这时l\u0026gt;\u003dn,那我们就得到了一个公共子串T\u0027[i-l+1 .. i]。这个子串在S中出现的次数是|endpos(u)|,又恰好包含T的循环同构串T\u0027[i-n+1 .. i]。\u003c/p\u003e \n \u003cp\u003e小Hi:基本思路是对的。但是要注意处理两个特殊情况。第一个情况是T的n个循环同构子串有重复(相同)的情况。比如T\u003d\"aa\",T\u0027\u003d\"aaa\",还是以S\u003d\"aabbabd\"为例\u003c/p\u003e \n \u003cpre\u003eS: aabbabd\r\nT\u0027: aaa\r\n1: a (u, l) \u003d (1, 1)\r\n2: aa (u, l) \u003d (2, 2), l\u0026gt;\u003dn\r\n3: aa (u, l) \u003d (2, 2), l\u0026gt;\u003dn\u003c/pre\u003e \n \u003cp\u003e小Hi:T\u0027[2]和T\u0027[3]结尾的最长公共子串都是\"aa\",(u, l)都是(2, 2)。我们要避免\"aa\"的出现次数被统计2次,小Ho你想想要怎么办?\u003c/p\u003e \n \u003cp\u003e小Ho:恩,我们要记录一个状态是不是之前在l\u0026gt;\u003dn的情况下到达过。如果到达过的话,下一次再到达就不要统计了。\u003c/p\u003e \n \u003cp\u003e小Hi:很好。我们还有第二个特殊情况要处理。那就是要区分串T\u0027[i-l+1 .. i]出现次数和T\u0027[i-n+1 .. i]的出现次数。前面说到,我们处理T\u0027[i]的时候求出当前状态u和匹配长度l。这时串T\u0027[i-l+1 .. i]一定是属于状态u的,T\u0027[i-l+1 .. i]的出现次数是|endpos(u)|。但是这时可能l\u0026gt;n,所以T\u0027[i-n+1 .. i]不一定属于状态u。T\u0027[i-n+1 .. i]是T\u0027[i-l+1 .. i]长度为n的后缀,可能在suffix-path(u-\u0026gt;S)上,出现次数比T\u0027[i-n+1 .. i]多。\u003c/p\u003e \n \u003cp\u003e小Ho:这个也好办,我们只要沿着suffix-path(u-\u0026gt;S)向上找,找到最靠近S的v满足maxlen[v]\u0026gt;\u003dn (也就是minlen[v]\u0026lt;\u003dn\u0026lt;\u003dmaxlen[v]),统计|endpos(v)|即可。\u003c/p\u003e \n \u003cp\u003e小Hi:这里有一个关键点,我们找到v之后可以直接令u\u003dv。以免每次向前找v的复杂度过高。 \u003c/p\u003e \n \u003cp\u003e小Ho:我试着总结一下,伪代码如下。\u003c/p\u003e \n \u003cpre\u003eans \u003d 0; //出现次数\r\nn \u003d length(T);\r\nT\u0027 \u003d T + T[1..n];\r\nu \u003d S, l \u003d 0;\r\nfor i \u003d 1 .. length(T\u0027):\r\n while u !\u003d S AND trans[u][T\u0027[i]] is NULL: //沿suffix-path(u-\u0026gt;S)找到一个状态v满足trans[v][T\u0027[i]]存在\r\n u \u003d slink[i], l \u003d maxlen[u];\r\n if trans[u][T\u0027[i]] is not NULL: \r\n u \u003d trans[u][T\u0027[i]], l++;\r\n else: //直到初始状态S都没有trans[v][T\u0027[i]]存在\r\n u \u003d S, l \u003d 0;\r\n if l \u0026gt; n: //要区分串T\u0027[i-l+1 .. i]出现次数和T\u0027[i-n+1 .. i]的出现次数\r\n while maxlen[slink[u]] \u0026gt;\u003d n:\r\n u \u003d slink[u], l \u003d maxlen[u];\r\n if l \u0026gt;\u003d n AND not visited[u]: //第一次在l\u0026gt;\u003dn的情况下达到u\r\n visited[u] \u003d TRUE;\r\n ans +\u003d |endpos(u)|;\u003c/pre\u003e \n \u003cp\u003e小Ho:最后一个问题,本题有多个T怎么办呐?\u003c/p\u003e \n \u003cp\u003e小Hi:笨!处理每个T复杂度都是线性的,多个T就依次处理一遍就行了。\u003c/p\u003e \n \u003cp\u003e小Ho:原来如此。\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第一行,一个由小写字母构成的字符串S,表示一部音乐作品。字符串S长度不超过100000。\u003c/p\u003e \n \u003cp\u003e第二行,一个整数N,表示有N段旋律。接下来N行,每行包含一个由小写字母构成的字符串str,表示一段旋律。所有旋律的长度和不超过 100000。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e输出共N行,每行一个整数,表示答案。\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003eabac\r\n3\r\na\r\nab\r\nca\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e2\r\n2\r\n1\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { max-width: 100%; }\r\n .fontweight {\r\n font-weight: bold;\r\n }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。\u003c/p\u003e \n \u003cp\u003e小Hi发现旋律可以循环,每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”,还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。\u003c/p\u003e \n \u003cp\u003e小Hi对此产生了浓厚的兴趣,他有若干段旋律,和一部音乐作品。对于每一段旋律,他想知道有多少在音乐作品中的子串(重复便多次计)和该旋律是“循环相似旋律”。\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e解题方法提示\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e解题方法提示\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:我们已经对后缀自动机比较熟悉了,今天我们再来道稍有难度的题。\u003c/p\u003e \n \u003cp\u003e小Ho:好!这道题目让我们求的是若干串在另一个长串S中各自作为子串出现的次数,只是匹配的方式从完全相等变成了“循环同构”。\u003c/p\u003e \n \u003cp\u003e小Hi:没错!如果匹配方式是完全相等的话,本题就可以使用AC自动机或者\u003ca href\u003d\"https://hihocoder.com/problemset/problem/1036\"\u003etrie图\u003c/a\u003e完美的解决。\u003c/p\u003e \n \u003cp\u003e小Ho:既然这个问题也和子串有关系,那么不妨试试后缀自动机。\u003c/p\u003e \n \u003cp\u003e小Hi:对。和上一期一样,你可以先想想如果询问只有一个串T应该怎么做。\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,那自然就考虑所有T的循环同构的串在长串S中出现的次数。\u003c/p\u003e \n \u003cp\u003e小Hi:没错。循环同构有点麻烦,如果我们枚举与T循环同构的串,再依次判断是否在S中出现过。那复杂度至少是O(length(T)^2)的了。\u003c/p\u003e \n \u003cp\u003e小Ho:恩。比如T\u003d\"abcd\"的话,我们要判断4个串\"abcd\", \"bcda\", \"cdab\", \"dabc\"在S中出现的次数。\u003c/p\u003e \n \u003cp\u003e小Hi:为了能顺利解决循环同构的问题。我们要做点准备,先考虑这么一个问题。\u003cspan class\u003d\"fontweight\"\u003e对于给定的字符串S和T,求S和T的最长公共子串\u003c/span\u003e。小Ho,你知道最长公共子串是什么吧? 要注意子串和子序列不同哦。\u003c/p\u003e \n \u003cp\u003e小Ho:知道。比如\"aabbabd\"和\"abbabb\"的最长公共子串就是\"abbab\"。\u003c/p\u003e \n \u003cp\u003e小Hi:我们利用SAM,可以做到对于T的每个位置i,都能求出以T[i]结尾的最长公共子串是什么。以你上面说的\"aabbabd\"和\"abbabb\"为例。我们可以求出\u003c/p\u003e \n \u003cpre\u003eS: aabbabd\r\nT: abbabb \r\n1:a\r\n2: ab\r\n3: abb\r\n4: abba\r\n5: abbab\r\n6: abb\u003c/pre\u003e \n \u003cp\u003e小Ho:这个怎么求呢?\u003c/p\u003e \n \u003cp\u003e小Hi:我们先构造S的后缀自动机。然后对于每个结束位置T[i],维护两个变量。一个是当前状态u,表示T[i]结尾的最长公共子串在S的SAM的哪个状态里;二是当前匹配长度l,表示T[i]结尾的最长公共子串的长度。初始时u\u003d初始状态S,l\u003d0。 \u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/f091cd6fecd83d6aecc52ab641a4933f?v\u003d1659761399\" title\u003d\"week131.png\"\u003e \n \u003cp\u003e小Hi:假设我们已经知道T[i-1]对应的(u, l),要求T[i]对应的(u\u0027, l\u0027)。如果trans[u][T[i]]存在的话,那么直接令u\u0027\u003dtrans[u][T[i]], l\u0027 \u003d l+1即可。\u003c/p\u003e \n \u003ctable class\u003d\"table table-bordered table-hover\" style\u003d\"width:70%;\"\u003e \n \u003cthead\u003e \n \u003ctr\u003e \n \u003cth\u003e位置\u003c/th\u003e \n \u003cth\u003eu\u003c/th\u003e \n \u003cth\u003el\u003c/th\u003e \n \u003c/tr\u003e \n \u003c/thead\u003e \n \u003ctbody\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[0]\u003c/td\u003e \n \u003ctd\u003eS\u003c/td\u003e \n \u003ctd\u003el\u003d0\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[1]\u003c/td\u003e \n \u003ctd\u003etrans[S][a]\u003d1\u003c/td\u003e \n \u003ctd\u003e1\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[2]\u003c/td\u003e \n \u003ctd\u003etrans[1][b]\u003d8\u003c/td\u003e \n \u003ctd\u003e2\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[3]\u003c/td\u003e \n \u003ctd\u003etrans[8][b]\u003d4\u003c/td\u003e \n \u003ctd\u003e3\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[4]\u003c/td\u003e \n \u003ctd\u003etrans[4][a]\u003d6\u003c/td\u003e \n \u003ctd\u003e4\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[5]\u003c/td\u003e \n \u003ctd\u003etrans[6][b]\u003d7\u003c/td\u003e \n \u003ctd\u003e5\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[6]\u003c/td\u003e \n \u003ctd\u003etrans[7][b]\u003dNULL\u003c/td\u003e \n \u003ctd\u003e?\u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e \n \u003c/table\u003e \n \u003cp\u003e小Ho:那如果遇到trans[u][T[i]]不存在怎么办? 比如处理的T[6]的时候,trans[7][b]不存在。\u003c/p\u003e \n \u003cp\u003e小Hi:这时我们要沿suffix-path(u-\u0026gt;S)找到一个状态v满足trans[v][T[i]]存在。所以先找suffix[7]\u003d8,而trans[8][b]\u003d4存在。这时令u\u003dtrans[v][T[i]], l\u003dmaxlen(v)+1。\u003c/p\u003e \n \u003ctable class\u003d\"table table-bordered table-hover\" style\u003d\"width:70%;\"\u003e \n \u003cthead\u003e \n \u003ctr\u003e \n \u003cth\u003e位置\u003c/th\u003e \n \u003cth\u003eu\u003c/th\u003e \n \u003cth\u003el\u003c/th\u003e \n \u003c/tr\u003e \n \u003c/thead\u003e \n \u003ctbody\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[0]\u003c/td\u003e \n \u003ctd\u003eS\u003c/td\u003e \n \u003ctd\u003el\u003d0\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[1]\u003c/td\u003e \n \u003ctd\u003etrans[S][a]\u003d1\u003c/td\u003e \n \u003ctd\u003e1\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[2]\u003c/td\u003e \n \u003ctd\u003etrans[1][b]\u003d8\u003c/td\u003e \n \u003ctd\u003e2\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[3]\u003c/td\u003e \n \u003ctd\u003etrans[8][b]\u003d4\u003c/td\u003e \n \u003ctd\u003e3\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[4]\u003c/td\u003e \n \u003ctd\u003etrans[4][a]\u003d6\u003c/td\u003e \n \u003ctd\u003e4\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[5]\u003c/td\u003e \n \u003ctd\u003etrans[6][b]\u003d7\u003c/td\u003e \n \u003ctd\u003e5\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[6]\u003c/td\u003e \n \u003ctd\u003etrans[7][b]\u003dNULL\u003c/td\u003e \n \u003ctd\u003e?\u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003eT[6]\u003c/td\u003e \n \u003ctd\u003etrans[suffix[7]][b]\u003dtrans[8][b]\u003d4\u003c/td\u003e \n \u003ctd\u003emaxlen[8]+1\u003d3\u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e \n \u003c/table\u003e \n \u003cp\u003e小Ho:这里trans[u][T[i]]不存在就沿着suffix-path(u-\u0026gt;S)向前找的过程好像类似\u003ca href\u003d\"https://hihocoder.com/problemset/problem/1015\"\u003eKMP\u003c/a\u003e中当前字符失配就沿next数组向前找? \u003c/p\u003e \n \u003cp\u003e小Hi:没错,过程是类似的。都是在\"abbab\"+\u0027b\u0027失配时,试图找到\"abbab\"的一个最长后缀s使得s+\u0027b\u0027不失配。我们知道\"abbab\"的后缀都在suffix-path(u-\u0026gt;S)里,所以沿着suffix-path(u-\u0026gt;S)向前找即可。\u003c/p\u003e \n \u003cp\u003e小Ho:如果最后直到初始状态S都没有trans[v][T[i]]存在呢?\u003c/p\u003e \n \u003cp\u003e小Hi:如果trans[S][T[i]]不存在,那字符T[i]肯定是没在字符串S中出现过。这时我们令u\u003dS, l\u003d0从T[i+1]重新开始即可。\u003c/p\u003e \n \u003cp\u003e小Hi:好了,现在对于T的每个位置i,我们都能求出以T[i]结尾的最长公共子串是什么。(严格来说我们知道最长公共子串的长度l)那我们能知道这个最长公共子串在S中出现了多少次么?\u003c/p\u003e \n \u003cp\u003e小Ho:这个我知道。我们既然已经知道子串对应的状态u,那么|endpos(u)|就是子串出现的次数。这个问题我们已经在\u003ca href\u003d\"https://hihocoder.com/problemset/problem/1449\"\u003ehiho一下 第129周\u003c/a\u003e学习过了。\u003c/p\u003e \n \u003cp\u003e小Hi:现在我们的准备工作做完了。小Ho你先回顾一下前面的内容,下面我们要开始解决这周的问题了。\u003c/p\u003e \n \u003cp\u003e小Ho:好的。\u003c/p\u003e \n \u003cp\u003e小Hi:现在我们要处理T的循环同构串们。这里有一个常用的技巧,假设T的长度是n,我们令T\u0027\u003dT + T[1..n-1]形成一个新的串T\u0027。例如对于\"abcd\",我们把\"abc\"拼在\"abcd\"后面,得到新的T\u003d\"abcdabc\"。这样\"abcd\"的循环同构串就变成了T\u0027\u003d\"abcdabc\"的长度为n的子串。 \u003c/p\u003e \n \u003cp\u003e小Ho:哦!然后我们再用之前讲的方法求出在每个位置T\u0027[i]结束的最长公共子串。我们可以求出对应的(u, l),如果这时l\u0026gt;\u003dn,那我们就得到了一个公共子串T\u0027[i-l+1 .. i]。这个子串在S中出现的次数是|endpos(u)|,又恰好包含T的循环同构串T\u0027[i-n+1 .. i]。\u003c/p\u003e \n \u003cp\u003e小Hi:基本思路是对的。但是要注意处理两个特殊情况。第一个情况是T的n个循环同构子串有重复(相同)的情况。比如T\u003d\"aa\",T\u0027\u003d\"aaa\",还是以S\u003d\"aabbabd\"为例\u003c/p\u003e \n \u003cpre\u003eS: aabbabd\r\nT\u0027: aaa\r\n1: a (u, l) \u003d (1, 1)\r\n2: aa (u, l) \u003d (2, 2), l\u0026gt;\u003dn\r\n3: aa (u, l) \u003d (2, 2), l\u0026gt;\u003dn\u003c/pre\u003e \n \u003cp\u003e小Hi:T\u0027[2]和T\u0027[3]结尾的最长公共子串都是\"aa\",(u, l)都是(2, 2)。我们要避免\"aa\"的出现次数被统计2次,小Ho你想想要怎么办?\u003c/p\u003e \n \u003cp\u003e小Ho:恩,我们要记录一个状态是不是之前在l\u0026gt;\u003dn的情况下到达过。如果到达过的话,下一次再到达就不要统计了。\u003c/p\u003e \n \u003cp\u003e小Hi:很好。我们还有第二个特殊情况要处理。那就是要区分串T\u0027[i-l+1 .. i]出现次数和T\u0027[i-n+1 .. i]的出现次数。前面说到,我们处理T\u0027[i]的时候求出当前状态u和匹配长度l。这时串T\u0027[i-l+1 .. i]一定是属于状态u的,T\u0027[i-l+1 .. i]的出现次数是|endpos(u)|。但是这时可能l\u0026gt;n,所以T\u0027[i-n+1 .. i]不一定属于状态u。T\u0027[i-n+1 .. i]是T\u0027[i-l+1 .. i]长度为n的后缀,可能在suffix-path(u-\u0026gt;S)上,出现次数比T\u0027[i-n+1 .. i]多。\u003c/p\u003e \n \u003cp\u003e小Ho:这个也好办,我们只要沿着suffix-path(u-\u0026gt;S)向上找,找到最靠近S的v满足maxlen[v]\u0026gt;\u003dn (也就是minlen[v]\u0026lt;\u003dn\u0026lt;\u003dmaxlen[v]),统计|endpos(v)|即可。\u003c/p\u003e \n \u003cp\u003e小Hi:这里有一个关键点,我们找到v之后可以直接令u\u003dv。以免每次向前找v的复杂度过高。 \u003c/p\u003e \n \u003cp\u003e小Ho:我试着总结一下,伪代码如下。\u003c/p\u003e \n \u003cpre\u003eans \u003d 0; //出现次数\r\nn \u003d length(T);\r\nT\u0027 \u003d T + T[1..n];\r\nu \u003d S, l \u003d 0;\r\nfor i \u003d 1 .. length(T\u0027):\r\n while u !\u003d S AND trans[u][T\u0027[i]] is NULL: //沿suffix-path(u-\u0026gt;S)找到一个状态v满足trans[v][T\u0027[i]]存在\r\n u \u003d slink[i], l \u003d maxlen[u];\r\n if trans[u][T\u0027[i]] is not NULL: \r\n u \u003d trans[u][T\u0027[i]], l++;\r\n else: //直到初始状态S都没有trans[v][T\u0027[i]]存在\r\n u \u003d S, l \u003d 0;\r\n if l \u0026gt; n: //要区分串T\u0027[i-l+1 .. i]出现次数和T\u0027[i-n+1 .. i]的出现次数\r\n while maxlen[slink[u]] \u0026gt;\u003d n:\r\n u \u003d slink[u], l \u003d maxlen[u];\r\n if l \u0026gt;\u003d n AND not visited[u]: //第一次在l\u0026gt;\u003dn的情况下达到u\r\n visited[u] \u003d TRUE;\r\n ans +\u003d |endpos(u)|;\u003c/pre\u003e \n \u003cp\u003e小Ho:最后一个问题,本题有多个T怎么办呐?\u003c/p\u003e \n \u003cp\u003e小Hi:笨!处理每个T复杂度都是线性的,多个T就依次处理一遍就行了。\u003c/p\u003e \n \u003cp\u003e小Ho:原来如此。\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第一行,一个由小写字母构成的字符串S,表示一部音乐作品。字符串S长度不超过100000。\u003c/p\u003e \n \u003cp\u003e第二行,一个整数N,表示有N段旋律。接下来N行,每行包含一个由小写字母构成的字符串str,表示一段旋律。所有旋律的长度和不超过 100000。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e输出共N行,每行一个整数,表示答案。\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003eabac\r\n3\r\na\r\nab\r\nca\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e2\r\n2\r\n1\u003c/pre\u003e \n\u003c/dd\u003e"}}]}