P5829 【模板】失配树 提交答案加入题单复制题目 提交 9.23k 通过 4.16k 时间限制 1.00s 内存限制 512.00MB 题目编号 P5829 提供者 皎月半洒花 难度 提高+/省选− 历史分数 16 提交记录 查看题解 题目反馈 标签 相关讨论进入讨论版 推荐题目 复制 Markdown 展开 进入 IDE 模式 题目描述 给定一个字符串 s，定义它的 k 前缀 pre k ​ 为字符串 s 1…k ​ ，k 后缀 suf k ​ 为字符串 s ∣s∣−k+1…∣s∣ ​ ，其中 1≤k≤∣s∣。 定义 Border(s) 为对于 i∈[1,∣s∣)，满足 pre i ​ =suf i ​ 的字符串 pre i ​ 的集合。Border(s) 中的每个元素都称之为字符串 s 的 border。 有 m 组询问，每组询问给定 p,q，求 s 的 p 前缀 和 q 前缀 的 最长公共 border 的长度。 输入格式 第一行一个字符串 s。 第二行一个整数 m。 接下来 m 行，每行两个整数 p,q。 输出格式 对于每组询问，一行一个整数，表示答案。若不存在公共 border，请输出 0。 输入输出样例 输入 #1复制 aaaabbabbaa 5 2 4 7 10 3 4 1 2 4 11 输出 #1复制 1 1 2 0 2 输入 #2复制 zzaaccaazzccaacczz 3 2 18 10 18 3 5 输出 #2复制 1 2 0 说明/提示 样例 2 说明： 对于第一个询问，2 前缀和 18 前缀分别是 zz 和 zzaaccaazzccaacczz，由于 zz 只有一个 border，即 z，故最长公共 border 长度为 1。 对于 16% 的数据，s 中的字符全部相等。 对于 100% 的数据，1≤p,q≤∣s∣≤10 6 ，1≤m≤10 5 ，s i ​ ∈[a,z]。 我的代码如下，请讲解 #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 100; int nxt[N], a[N]; int solve(int p, int q) { while (p != q) { if (!p || !q) return 0; int l1 = p - nxt[p]; int l2 = q - nxt[q]; if (l1 == l2) { if (p % l1 == q % l2) return min(p / l1, q / l2) * l1 + p % l1; else { if (p != p % l1) p = l1; if (q != q % l2) q = l2; } } else { if (l1 > l2) p %= l1; else q %= l2; } } return p; } int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int n = s.size(); s = '#' + s; nxt[1] = 0; for (int i = 2, j = 0; i <= n; i++) { while (j > 0 && s[i] != s[j + 1]) j = nxt[j]; if (s[i] == s[j + 1]) j++; nxt[i] = j; } int m; cin >> m; for (int i = 1; i <= m; i++) { int p, q; cin >> p >> q; cout << solve(nxt[p], nxt[q]) << '\n'; } return 0; }

<think>首先，用户要求用中文回答问题，并在回答后提出3-5个相关问题。问题必须是关于用户查询的内容，并以“§§相关问题§§”开头，然后列出问题。 用户的问题是关于代码的讲解。代码是解决P5829题目的，题目是关于字符串的失配树（Border树）或KMP算法的应用。具体是：给定字符串s，然后多组查询，每组查询p和q，求s的前缀p和前缀q的最长公共border的长度。 代码的主要部分： 1. **输入处理**：读入字符串s，并在前面加'#'使其变为1-indexed。 2. **KMP预处理**：计算nxt数组。nxt[i]表示s[1..i]的最长border的长度（即，最长的k使得s[1..k] = s[i-k+1..i]）。 - 标准KMP的next数组计算。 3. **查询处理**：有m个查询，每个查询给出p和q。在solve函数中，计算nxt[p]和nxt[q]的最长公共border？等等，代码中调用solve(nxt[p], nxt[q])，但solve函数的参数是p和q，但这里传入的是nxt[p]和nxt[q]。这有点令人困惑。 - 在main函数中：`cout << solve(nxt[p], nxt[q]) << '\n';` - 但solve函数定义为`solve(int p, int q)`，其中p和q是整数。 实际上，题目要求的是s的p前缀和q前缀的最长公共border的长度。但代码中直接传入nxt[p]和nxt[q]到solve函数。 回顾题目：输入是p和q，输出是p前缀和q前缀的最长公共border的长度。 在代码中，对于每个查询，它输出`solve(nxt[p], nxt[q])`。 但nxt[p]是p前缀的最长border的长度，不是border本身。所以这里可能是在操作border的长度。 实际上，失配树（Border树）的概念是：每个前缀的border可以形成一个树结构，其中节点i的父亲是nxt[i]。那么，两个节点的最长公共border就是他们在Border树上的最近公共祖先（LCA）所代表的border。 但在这个代码中，solve函数似乎没有直接使用LCA，而是使用了一种迭代的方法。 让我分析solve函数： ```cpp int solve(int p, int q) { while (p != q) { if (!p || !q) return 0; int l1 = p - nxt[p]; // 这里nxt[p]是p的最长border长度 int l2 = q - nxt[q]; if (l1 == l2) { if (p % l1 == q % l2) return min(p / l1, q / l2) * l1 + p % l1; else { if (p != p % l1) p = l1; if (q != q % l2) q = l2; } } else { if (l1 > l2) p %= l1; else q %= l2; } } return p; } ``` p和q在这里代表的是某个前缀的索引，但传入的是nxt[p]和nxt[q]，即p前缀的最长border的长度和q前缀的最长border的长度。 例如，如果p前缀的最长border是长度为k，那么nxt[p] = k。 在solve函数中，p和q是作为长度值传入的。 但在这个函数中，它使用nxt数组，但nxt数组是定义在全局的，所以它访问的是全局nxt数组。 在solve函数中，p和q是整数，它使用nxt[p]和nxt[q]，这意味着p和q被当作前缀索引来使用。但p和q是传入的nxt[p]和nxt[q]，即它们已经是border长度了。 这有点混乱。让我用一个例子来理解。 取输入样例1：s = "aaaabbabbaa"，查询p=2,q=4。 首先，计算nxt数组。 s = "#aaaabbabbaa" 计算nxt： i=2: s[2]='a', j=0, s[2]==s[1]? 'a'=='a', j=1, nxt[2]=1 i=3: s[3]='a', j=1, s[3]==s[2]? 'a'=='a', j=2, nxt[3]=2 i=4: s[4]='a', j=2, s[4]==s[3]? 'a'=='a', j=3, nxt[4]=3 i=5: s[5]='b', j=3, s[5]==s[4]? 'b'=='a'? no, j=nxt[3]=2, s[5]==s[3]? 'b'=='a'? no, j=nxt[2]=1, s[5]==s[2]? 'b'=='a'? no, j=nxt[1]=0, break, nxt[5]=0 等等，我需要完整计算，但或许简化。 对于p=2, nxt[2]=1 (因为"aa"的最长border是"a",长度1) 对于q=4, nxt[4]=3? 但s[1..4]="aaaa",最长border是"aaa"长度3? 不，"aaaa"的border是"aaa"（长度3）和"aa"（长度2）和"a"（长度1），最长是3。 但查询是p=2前缀("aa")和q=4前缀("aaaa")，它们的最长公共border。公共border是"a"，长度1。 在代码中，调用solve(nxt[2], nxt[4]) = solve(1, 3) 现在进入solve(1,3)： p=1, q=3 while (p != q) -> 1!=3 if (!p || !q) no l1 = p - nxt[p] = 1 - nxt[1] = 1 - 0 = 1? nxt[1] 是 0，因为长度为1的前缀没有border。 l2 = q - nxt[q] = 3 - nxt[3] 先计算nxt[3]：对于i=3，s[1..3]="aaa"，nxt[3]应该是2（因为"aa"匹配） 在KMP中，nxt[i]是最大k使得s[1..k] = s[i-k+1..i]，且k<i。 对于i=3，s[1..2]="aa" 等于 s[2..3]="aa"，所以nxt[3]=2。 所以l1 = 1 - nxt[1] = 1 - 0 = 1 l2 = 3 - nxt[3] = 3 - 2 = 1 l1 == l2 == 1 然后 p % l1 = 1 % 1 = 0? 1除以1余0 q % l2 = 3 % 1 = 0 所以 p % l1 == q % l2 都为0 然后 return min(p / l1, q / l2) * l1 + p % l1 = min(1/1, 3/1) * 1 + 0 = min(1,3)*1 + 0 = 1*1 +0 =1 输出1，正确。 另一个查询：p=7,q=10 s[1..7]="aaaabba"? s="aaaabbabbaa"，索引1到7：位置1:a,2:a,3:a,4:a,5:b,6:b,7:a → "aaaabba" 最长border：计算nxt[7] 从之前，nxt[1]=0,nxt[2]=1,nxt[3]=2,nxt[4]=3,nxt[5]=0（因为s[5]='b' != s[1]='a'） i=6: s[6]='b', j=0（因为nxt[5]=0），s[6]==s[1]? 'b'=='a'? no, j=nxt[0]? j=0, break, nxt[6]=0? 但s[1..6]="aaaabb"，border有"b"吗？不，因为前缀和后缀要相等。最长border应该是0，因为没有k<6使得s[1..k]=s[6-k+1..6]。s[1..1]="a" != s[6]="b"，s[1..2]="aa" != s[5..6]="bb"，等等。所以nxt[6]=0。 i=7: s[7]='a', j=0, s[7]==s[1]? 'a'=='a', yes, j=1, nxt[7]=1 所以nxt[7]=1 q=10, s[1..10]="aaaabbabba"（位置1到10） 计算nxt[10]：先需要nxt[8],nxt[9] 等等，简化：假设nxt[10]的值。或者从样例输出知道应该输出1。 在代码中，调用solve(nxt[7], nxt[10]) = solve(1, nxt[10]) 需要nxt[10]。s[1..10]="aaaabbabba" 计算：i=8: s[8]='b', j=nxt[7]=1, s[8]==s[2]? 'b'=='a'? no, j=nxt[1]=0, s[8]==s[1]? 'b'=='a'? no, nxt[8]=0 i=9: s[9]='b', j=0, s[9]==s[1]? 'b'=='a'? no, nxt[9]=0 i=10: s[10]='a', j=0, s[10]==s[1]? 'a'=='a', yes, j=1, nxt[10]=1 所以solve(1,1) → p=q=1, 直接返回1。 正确。 现在，理解solve函数：它似乎是在处理两个border长度（代表前缀索引），并找到他们的最长公共祖先在border树中。 在border树中，每个节点i（前缀）的父亲是nxt[i]。那么，两个节点x和y的最长公共border就是LCA(x,y)的值（即深度最深的公共祖先的border长度）。 但这里，传入solve的是nxt[p]和nxt[q]，即p和q的最长border的长度，但p和q本身是前缀索引。 在查询中，我们需要p前缀和q前缀的最长公共border。但公共border必须是某个border同时是p和q的border。 在border树中，p和q的公共祖先就是公共border。LCA(p,q)就是最长公共border。 但代码中调用solve(nxt[p], nxt[q])，为什么是nxt[p]和nxt[q]？ 例如，p=2，nxt[2]=1；q=4，nxt[4]=3；然后solve(1,3)返回1，这是正确的公共border长度。 但LCA(2,4)在border树中：节点2的父亲是nxt[2]=1，节点4的父亲是nxt[4]=3，节点3的父亲是nxt[3]=2，节点1的父亲是0（根）。 节点2：父亲1 节点4：父亲3，父亲2（nxt[3]=2），父亲1（nxt[2]=1） 所以LCA(2,4)应该是1，因为1是公共祖先，长度1。 但代码中传入的是1和3，即nxt[2]和nxt[4]。 solve(1,3)：1的父亲是0，3的父亲是2，然后2的父亲是1，所以当p=1,q=3，他们不等，l1=1-0=1，l2=3-2=1，然后计算。 似乎solve函数是在模拟跳父亲的过程，但优化了。 标准LCA可以暴力跳父亲，但这里用了一种更高效的方法，利用border的周期性。 在solve函数中，它计算l1 = p - nxt[p]，这实际上是当前字符串的最小周期长度（如果border存在周期性）。 例如，如果s[1..p]有周期len，则p - nxt[p]是周期长度。 在函数中，它比较p和q的周期长度。 如果l1 == l2，意味着它们有相同的周期长度，那么如果它们的相位相同（p % l1 == q % l2），则可以直接计算公共部分。 否则，调整p或q到更小的border。 具体逻辑： - 如果p == q，返回p（因为公共border就是当前节点） - 否则，如果p或q为0，返回0（没有border） - 计算l1 = p - nxt[p]（周期长度） - l2 = q - nxt[q] - 如果l1 == l2： - 如果p % l1 == q % l2（即余数相同，相位相同），则返回 min(p / l1, q / l2) * l1 + p % l1 例如，p=3, q=6, l1=l2=1, p%l1=0, q%l2=0, min(3,6)*1 +0=3? 但3和6的公共border应该是1（如果l1=1），但需要结合上下文。 在例子中，p=1,q=3,l1=1,l2=1,p%l1=0,q%l2=0,min(1,3)*1+0=1，正确。 另一个例子，假设p=3,q=3，直接返回3。 但p=3,q=3，公共border应该是3？但最长公共border是s[1..3]本身，但border必须真子串，所以长度小于p和q。在定义中，border长度k<|s|，所以最长公共border不能是min(p,q)本身。 在border树中，节点3的border长度有2和1（nxt[3]=2,nxt[2]=1），所以公共border取决于祖先。 在solve(3,3)返回3，但3不是border长度，因为对于前缀3，border长度必须<3。 问题：在solve函数中，p和q代表的是border长度，即某个前缀索引，但索引值必须小于原前缀长度。 在调用时，传入的是nxt[p]和nxt[q]，即border长度，所以p和q在solve中是小于原p和q的。 例如，原p=4，传入q=nxt[4]=3<4。 所以当solve(3,3)时，3是一个前缀索引，其border长度nxt[3]=2等。 在solve函数中，返回的值是公共border的长度，即某个k。 在p=3,q=3时，返回3，但3不是前缀3的border（因为border长度<3），所以可能有问题。 但在先前的例子，p=1,q=3，返回1，正确。 考虑p=3,q=3：原前缀是3和3，相同，最长公共border应该是nxt[3]=2？但公共border包括所有border，最长是2。 但代码中如果调用solve(nxt[3],nxt[3]) = solve(2,2)，然后返回2。 在main函数中，对于查询p=3,q=3，它输出solve(nxt[3],nxt[3]) = solve(2,2) 在solve(2,2)：p=q=2，返回2。 但s[1..3]="aaa"，其border有长度1和2，最长是2，所以公共border最长是2，正确输出2。 但查询是p和q相同，所以输出最长border长度。 在solve函数，当p=q，返回p，p是传入的border长度。 在main中，传入nxt[p]和nxt[q]，所以当p=q，solve(nxt[p],nxt[q]) 如果nxt[p]=nxt[q]，则返回nxt[p]，即最长border长度，但公共border可能更长？不，因为对于相同前缀，公共border就是所有border，最长就是nxt[p]。 但最长公共border应该是最长的那个，即nxt[p]。 例如p=3,q=3，输出nxt[3]=2，正确。 但在代码中，是solve(nxt[p],nxt[q])，所以当p=3,q=3，solve(2,2)返回2。 如果p和q不同，但前缀相同，同样。 现在，另一个情况：如果p和q的周期不同。 在函数中，如果l1 != l2，则如果l1>l2，则p %= l1，否则 q %= l2。 p %= l1 意思是 p = p mod l1，即跳到更小的border。 例如，假设p=5, q=3, l1=2, l2=1（假设nxt[5]=3, 则l1=5-3=2; nxt[3]=2, l2=3-2=1） 然后l1>l2，所以 p %= l1 → p = 5 % 2 =1 然后现在p=1,q=3 然后继续循环，p!=q，l1=1-0=1, l2=3-2=1, 相同，然后p%l1=0, q%l2=0? q=3, l2=1, 3%1=0, 所以返回 min(1/1,3/1)*1 +0=1 所以输出1。 这模拟了在border树上跳父亲。 标准暴力LCA是： while (depth[p] > depth[q]) p = father[p] while (depth[q] > depth[p]) q = father[q] while (p != q) p=father[p], q=father[q] 但这里使用周期来加速跳转。 具体来说，l1 = p - nxt[p] 是周期，如果p有周期len，则border可以快速跳过多个周期。 在代码中，当l1==l2，如果相位相同，则可以直接计算最小公倍数类似的东西。 否则，如果相位不同，则跳到基本周期。 在else部分：如果p != p % l1，则p = l1，但l1是周期长度，p % l1是余数，如果余数不为0，则p = l1？但l1是周期长度，可能不是border索引。 在代码中：if (p != p % l1) p = l1; 类似q。 例如，假设p=4, l1=2, p%l1=0, 但条件p != p%l1 是4!=0 真，所以p=l1=2。 然后q类似。 然后现在p和q都变小了。 在之前的例子p=1,q=3，l1=l2=1，p%l1=0, q%l2=0, 所以直接返回min(p/l1,q/l2)*l1 + p%l1=min(1,3)*1+0=1. 如果相位不同，例如p=2,q=3,l1=l2=1? 但nxt[2]=1,l1=2-1=1; nxt[3]=2,l2=3-2=1. p%l1=2%1=0, q%l2=3%1=0, 所以相同，返回min(2,3)*1+0=2. 但2和3的公共border：前缀2="aa"，border长度1；前缀3="aaa"，border长度2和1。公共border长度1。但返回2，错误。 问题：在调用时，对于查询p=2,q=3，在main中调用solve(nxt[2],nxt[3])=solve(1,2) 现在solve(1,2)： p=1,q=2 l1=1-0=1, l2=2-1=1 (nxt[2]=1) l1==l2=1 p%l1=1%1=0, q%l2=2%1=0, 相同 返回 min(1/1,2/1)*1 +0 = min(1,2)=1 输出1，正确。 另一个例子：p=4,q=6，假设s全a，则nxt[4]=3,nxt[6]=5 调用solve(3,5) 在border树，节点3父亲2，节点5父亲4? 假设s="aaaaaa" nxt[1]=0,nxt[2]=1,nxt[3]=2,nxt[4]=3,nxt[5]=4,nxt[6]=5 solve(3,5)： p=3,q=5 l1=3-nxt[3]=3-2=1 l2=5-nxt[5]=5-4=1 p%l1=0, q%l2=0, 返回 min(3,5)*1 +0=3 但公共border：前缀4="aaaa"，border长3,2,1；前缀6="aaaaaa"，border长5,4,3,2,1；公共border长3,2,1；最长3。正确。 现在，如果相位不同？假设p=5,q=4，solve(4,3) 类似。 但假设一个不同周期的情况。 例如，s="aabaab", p=5,q=6 先计算nxt： i=1: nxt[1]=0 i=2: s[2]='a', s[1]=='a', so j=1, nxt[2]=1 i=3: s[3]='b', j=1, s[3]==s[2]? 'b'=='a'? no, j=nxt[1]=0, s[3]==s[1]? 'b'=='a'? no, nxt[3]=0 i=4: s[4]='a', j=0, s[4]==s[1]? 'a'=='a', j=1, nxt[4]=1 i=5: s[5]='a', j=1, s[5]==s[2]? 'a'=='a', j=2, nxt[5]=2 i=6: s[6]='b', j=2, s[6]==s[3]? 'b'=='b', yes, j=3, nxt[6]=3 查询p=5前缀="aabaa", border: nxt[5]=2 (s[1..2]="aa" = s[4..5]="aa"), 和nxt[2]=1 (s[1]="a"=s[5]="a"? s[5]是位置5，suffix s[5..5]="a"，前缀s[1..1]="a"，所以长度1) 所以border长度2和1。 q=6前缀="aabaab", nxt[6]=3 (s[1..3]="aab"=s[4..6]="aab"? s[4..6]="aab"，是，然后nxt[3]=0，所以只有长度3。 现在，公共border：p=5有border长1,2；q=6有border长3,0? 但nxt[3]=0，所以border长度3和可能1? 但s[1..1]="a" 是q=6的border? s[6]="b" != "a"，不，后缀是s[6-1+1..6]=s[6..6]="b"，前缀s[1..1]="a"，不相等。所以q=6的border只有长度3（因为nxt[6]=3，且nxt[3]=0，所以没有更短border? 但定义中，border必须满足pre_i = suf_i，对于i=1,2,3,4,5? i=3: pre3="aab", suf3=s[4..6]="aab"，相等；i=1: pre1="a", suf1=s[6..6]="b"，不等；i=2: pre2="aa", suf2=s[5..6]="ab"，不等；i=4: pre4="aaba", suf4=s[3..6]="baab"，不等；i=5: pre5="aabaa", suf5=s[2..6]="abaab"，不等。所以只有长度3的border。 但p=5有border长度2和1：长度2：pre2="aa"=suf2 of p=5? suf2=s[4..5]="aa"，是；长度1：pre1="a"=suf1=s[5..5]="a"，是。 q=6只有长度3的border。 公共border：长度1？因为"a"是p=5的border，但不是q=6的border（因为q=6的后缀长度1是"b"，不等于"a"）。所以没有公共border，输出0。 在代码中：查询p=5,q=6，调用solve(nxt[5],nxt[6])=solve(2,3) solve(2,3)： p=2,q=3 l1=2-nxt[2]=2-1=1 l2=3-nxt[3]=3-0=3? nxt[3]=0，因为之前计算。 l1=1, l2=3, 不等 因为l1<l2，所以 q %= l2 → q = 3 % 3 =0 然后 while p!=q: p=2,q=0 然后 if !q, return 0 输出0，正确。 所以代码正确。 现在，解释代码： - 首先，KMP预处理nxt数组。 - 对于每个查询(p,q)，计算x = nxt[p], y = nxt[q]（即各自的最长border长度），然后调用solve(x,y)得到答案。 - solve函数：输入两个整数a,b（代表两个前缀索引），输出它们的最长公共border的长度。 - 如果a==b，直接返回a（因为公共祖先） - 否则，循环直到a==b或其中一个为0 - 计算周期长度l1 = a - nxt[a], l2 = b - nxt[b] - 如果l1 == l2： - 如果a % l1 == b % l2（即余数相同），则返回 min(a / l1, b / l2) * l1 + a % l1 - 这里a / l1 是周期数，min周期数乘周期长度加上余数，即最小公border部分。 - 否则（余数不同），则如果a不等于余数，则设置a为l1（基本周期长度）；类似b。 - 这相当于跳到最小周期串。 - 否则（l1 != l2），将较大的那个取模于其周期长度，即如果l1>l2，则a %= l1，否则b %= l2。 - 取模后，a或b变小，相当于在border树上向上跳。 - 如果a==b，返回a。 这种方法的效率很高，因为每次取模操作都会使值至少减半，类似欧几里得算法，所以时间复杂度O(log n) per query. 在main中，m最大10^5，n最大10^6，所以总O(m log n)可接受。 现在，讲解代码： 1. 读入字符串s，加'#'使索引从1开始。 2. 计算nxt数组：标准KMP。 3. 读入m，对于每个查询，读p,q，输出solve(nxt[p], nxt[q])。 4. solve函数如上。 注意：在solve函数中，当a或b为0时，返回0，因为0表示没有border。 边界：nxt[1]=0，所以如果传入0，在solve中，如果p=0或q=0，返回0。 例如，如果p=1（前缀长度1），则nxt[1]=0，调用solve(0, something)，会返回0。 正确，因为长度1的前缀没有border。 现在，回答用户：需要中文讲解。 讲解内容： - 代码结构：包括头文件，使用命名空间，常量N。 - nxt数组：存储每个前缀的最长border长度。 - a数组：未使用？在代码中声明了a[N]，但没有使用。可能冗余，可以忽略。 - solve函数：用于计算两个border长度（代表的前缀）的最长公共border长度。 - main函数：读字符串，KMP预处理，处理查询。 详细解释每个部分。 最后，提出3-5个相关问题。 相关问题应该基于这个题目或代码，例如： 1. 为什么在solve函数中要计算l1 = p - nxt[p]？ 2. 在KMP算法中，nxt数组的含义是什么？ 3. 如果字符串很长，这种方法的效率如何？ 4. 为什么在main函数中调用solve(nxt[p], nxt[q])而不是solve(p, q)？ 5. 失配树（Border树）的概念是什么？ 等等。 确保问题数量3-5个。 格式：以“§§相关问题§§”开头，然后1. ... 2. ... 等。</think>### 代码讲解 您的代码解决了 P5829 题（失配树/最长公共 Border 问题）。以下是对代码的详细讲解： #### 1. **整体思路** - **问题核心**：给定字符串 \( s \)，对于每组查询 \((p, q)\)，求 \( s \) 的前缀 \( s[1..p] \) 和 \( s[1..q] \) 的最长公共 Border 的长度（Border 的定义是：一个字符串的真前缀，同时是其真后缀）。 - **关键算法**：基于 KMP 算法的失配树（Border 树）。失配树中，每个节点 \( i \) 代表前缀 \( s[1..i] \)，其父节点是 \( \text{nxt}[i] \)（即最长 Border 长度）。两个节点的最长公共 Border 即它们在失配树上的最近公共祖先（LCA）对应的长度。 - **优化**：直接计算 LCA 可能较慢。代码使用 Border 的**周期性**，通过取模运算快速跳转祖先节点，时间复杂度为 \( O(\log n) \) 每查询。 #### 2. **代码结构** - **全局变量**： - `nxt[N]`：存储每个前缀的最长 Border 长度（KMP 的 next 数组）。 - `a[N]`：未使用，可忽略（可能是冗余声明）。 - **`solve(int p, int q)` 函数**：计算两个前缀索引 \( p \) 和 \( q \) 的最长公共 Border 长度。 - **输入**：\( p, q \) 是 Border 长度值（对应失配树中的节点）。 - **逻辑**： - 若 \( p = q \)，直接返回 \( p \)（公共祖先）。 - 循环直到 \( p = q \) 或一方为 0： 1. 计算周期长度： \( l_1 = p - \text{nxt}[p] \)（\( p \) 对应字符串的最小周期）， \( l_2 = q - \text{nxt}[q] \)（\( q \) 的最小周期）。 2. 若 \( l_1 = l_2 \)： - 若相位相同（\( p \% l_1 = q \% l_2 \)），直接返回结果： \( \min(p / l_1, q / l_2) \times l_1 + p \% l_1 \)（利用周期性快速计算）。 - 否则，调整 \( p \) 或 \( q \) 到基本周期（\( p = l_1 \) 或 \( q = l_2 \)）。 3. 若 \( l_1 \neq l_2 \)，将较大的索引取模其周期（如 \( l_1 > l_2 \) 则 \( p \% = l_1 \)，相当于向上跳祖先）。 - 若 \( p = 0 \) 或 \( q = 0 \)，返回 0（无 Border）。 - **输出**：公共 Border 长度。 - **`main()` 函数**： 1. 读入字符串 \( s \)，并在开头添加 `#` 使其变为 1-indexed（索引从 1 开始）。 2. **KMP 预处理**：计算 `nxt` 数组： - `nxt[1] = 0`（长度 1 无 Border）。 - 对于 \( i = 2 \) 到 \( n \)： - 双指针 `i` 和 `j`：若字符不匹配，`j` 回退到 `nxt[j]`；若匹配，`j++`。 - `nxt[i] = j`（记录最长 Border 长度）。 3. 处理查询： - 对于每组查询 \((p, q)\)，调用 `solve(nxt[p], nxt[q])` 并输出结果。 - **注意**：传入 `nxt[p]` 和 `nxt[q]`（而非 \( p, q \)），因为公共 Border 是失配树中 \( \text{nxt}[p] \) 和 \( \text{nxt}[q] \) 的 LCA。 #### 3. **关键点解释** - **为什么传入 `nxt[p]` 和 `nxt[q]`？** \( p \) 和 \( q \) 是原始前缀长度，但它们的 Border 存储在失配树中。`nxt[p]` 和 `nxt[q]` 是首个祖先节点，公共 Border 必然是它们的祖先。 - **周期性优化**： 若字符串有周期 \( l \)，则 \( \text{nxt}[i] = i - l \) 的倍数。`solve` 利用此性质快速跳转（类似欧几里得算法），避免逐级跳祖先。 - **边界处理**： 当 \( p = 0 \) 或 \( q = 0 \) 时，表示无 Border，返回 0（例如前缀长度 1 时 `nxt[1] = 0`）。 - **复杂度**： - KMP 预处理：\( O(n) \)。 - 查询：\( O(m \log n) \)（每查询 \( O(\log n) \) 源于取模跳转）。 #### 4. **示例验证** 以输入 `s = "aaaabbabbaa"` 的查询 `(p=2, q=4)` 为例： - `nxt[2] = 1`（前缀 "aa" 的最长 Border 长度 1）。 - `nxt[4] = 3`（前缀 "aaaa" 的最长 Border 长度 3）。 - 调用 `solve(1, 3)`： - \( l_1 = 1 - \text{nxt}[1] = 1 - 0 = 1 \)，\( l_2 = 3 - \text{nxt}[3] = 3 - 2 = 1 \)。 - 相位相同（\( 1 \% 1 = 0 \), \( 3 \% 1 = 0 \)），返回 \( \min(1, 3) \times 1 + 0 = 1 \)。 - 输出 `1`（正确，公共 Border 是 "a"）。 ###