题目

首先发现有一个 \(a[j \cdots n] + b [1 \cdots i]\) 的东西，很自然的可以考虑到把 \(b\) 接到 \(a\) 后面得到 \(s=a+b\)。然后 \(a[j \cdots n] + b[1 \cdots i]\) 就可以在 \(S\) 中表示为经过拼接分界点的一个子串。

因此题目转化为判定二元组 \((i,j)\) 是否满足下图的匹配关系：

其中 \(a[j \cdots n] , b [1 \cdots i]\) 为上文中所述跨过 \(s\) 拼接分界点的连续子串，左端点为 \([1,n]\) 中的 \(j\)，右端点为 \([n+1,2n]\) 中的 \(i\)。注意到此时对两串的长度并没有限制。

因此只需判定：在左边从 \(j\) 开始，是否可以找到长度为 \(i\) 的匹配满足 \(s\) 中 \(j\) 开始的 \(i\) 个字符是否与 \(a[1 \cdots i]\) 相同，右边的 \(i\) 结尾的后缀类似，只需要找 \(s\) 中 \(n+i\) 开始向前的 \(n-j+1\) 个字符是否与 \(b[j \cdots n]\) 相同。然后可以发下只需要找到 \(s[j:]\) 与 \(a\) 的 \(LCP\)，记作 \(p1_j\)，再找到 \(s[:n+i]\) 与 \(b\) 的 \(LCS\)，记作 \(p2_i\)，则 \(a[j \cdots n] + b[1 \cdots i] = a[1 \cdots i] + b[j \cdots n]\) 当且仅当：

这就是一个二维数点。所以用 Z Algorithm 处理出 \(s\) 的所有后缀与 \(a\) 的 \(LCP\)，以及 \(s\) 的所有前缀与 \(b\) 的 \(LCS\)，最后用排序+树状数组离线二维数点即可。时间复杂度：Z Algorithm 为线性，树状数组单 \(\log\)，总复杂度 \(O(n \log n)\)。

总结：如果出现：一个串的后缀，后面拼接一个串的前缀的形式，可以考虑将两个原串按顺序拼接，之后第一个串的后缀拼接上第二个串的前缀就可以用新串（原串相拼的结果）的一个跨越拼接分界点的子串表示。这样就可以转为处理连续子串，会方便很多。