题解

思路

Z 函数要求把模式串与它的每个后缀比较；扩展数组要求把同一模式串与文本串的每个后缀比较。若逐个位置重新比较，会反复扫描大量已经确认相等的区间。

维护当前已知最靠右的匹配区间 $[l,r]$。处理新位置 $i$ 时，若 $i\le r$，可利用模式串中对应位置已经求出的答案作为初值，但不能越过 $r$；随后只从区间右端继续比较。若得到更靠右的匹配区间，就更新 $l,r$。

做法

先在线性时间求模式串 $b$ 的 Z 数组，并令 $z_1=|b|$。再用相同的 Z 盒维护方法扫描文本串 $a$：盒内位置从 $b$ 的 Z 数组取得可复用长度，盒外只继续比较尚未确认的字符，得到扩展数组 $p$。

最后按下标从 $1$ 开始计算两个数组的异或权值。乘法使用 64 位无符号整数，避免最大长度下的乘积溢出。

正确性证明

对于任一位置 $i$，若它在当前匹配区间外，算法从长度零开始直接比较，显然得到真实最长公共前缀。

若 $i$ 位于 $[l,r]$ 内，则区间定义保证文本片段与模式串前缀相等，因此模式串中对应位置的已知 Z 值可以安全复用到 $r$ 为止。若该值未触及右端，答案已完全确定；若触及右端，算法从 $r+1$ 继续逐字符比较，直到第一次失配或字符串结束。因此每个位置得到的长度既全部匹配，也不能再延长，正是最长公共前缀。

同一论证分别适用于模式串自身的 Z 数组和文本串的扩展数组。最终权值逐项采用题目定义计算，所以输出正确。

复杂度

设 $N=|a|+|b|$。每次显式字符比较都会推进某个最右端点，时间复杂度为 $O(N)$；保存两个数组和字符串的空间复杂度为 $O(N)$。