转化一下题意，你需要给 $S(a)$ 和 $S(b)$ 中的串两两匹配，$s$ 和 $t$ 匹配的贡献是它们的最长公共前缀，要求最大化贡献和。

贡献和的最大值有一个显然的上界，对于每个前缀 $s$，求出 $S(a),S(b)$ 中以 $s$ 为前缀的串个数 $c_1,c_2$，则 $s$ 的贡献就是 $\min(c_1,c_2)$，贡献的总和就是上界，且这个上界是存在构造的，建出 Trie 树然后从叶子到根每次尽量匹配子树中的点即可。

但是由于 $S(a),S(b)$ 中的串长总和是 $O(n^2)$ 级别的，所以我们无法直接构造出整个 Trie。我们考虑尽量节省的去保存子串信息，这就需要用到后缀自动机了。但是注意到可以作为前缀的串需要满足起始点在 $[1,n-k+1]$ 内，这是不好使用 SAM 记录的，我们可以将整个串反转，这样就变成 endpos 在 $[k,n]$ 内，就容易查询 $c_1,c_2$ 的值了。

时间复杂度 $O(n)$。