SP25480 TAP2015I - Invading aliens

在弗雷德·霍伊尔和约翰·艾略特的小说《安德洛墨达》中，仙女座星系中一颗距离我们 200 光年的星球上的文明决定进行星际殖民。为避免昂贵而漫长的星际旅行，他们选择发送信号，而非飞船进行远程殖民。这些信号包含建造超级计算机（其中包含能够统治其他文明的人工智能）的指令，虽然这不是我们现在要解决的问题。 人类在建造这台超级计算机之前，必须解码这些来自外星的信号。外星人通过两种不同频率发送的信号各包含一个长度为 $N$ 的代码，该代码在信号中无限重复。例如，当 $N = 3$，如果一个代码是 "abc"，那么接收到的信号就是 "...cabcabcabcab..."，其中省略号表示代码向前后无尽地重复。由于这点，地球接收到的信号中可能���在多个可以与之匹配的代码。例如，针对 $N = 3$，可能的代码有 "abc"、"bca" 和 "cab"。 更复杂的是，两个频率上传输的消息由 'a' 到 'z' 组成，但每个字符在两个频率上传输时对应关系不明确。换句话说，字符在一个频率中可以被另一频率中字符替代，这是通过一种从 1 到 26 的任意排列来实现的。比如，若 $\sigma(1) = 24$，$\sigma(2) = 25$ 和 $\sigma(3) = 26$，那么代码 "abc" 在另一频率中可能变为 "xyz"，因此该频率信号就是 "...zxyzxyzxyzxy..."。 你的任务是解码这个外星信号，找出可能与这两个频率所接收到的信号匹配的代码中最长的公共子串长度。具体来说，你需要确定最大值 $K$，使得存在两个兼容接收到的信号的代码，分别记作 $a_1 a_2 \ldots a_N$ 和 $b_1 b_2 \ldots b_N$，使它们在允许字符排列变化的情况下，存在 $0 \leq i, j < N$ 满足对于 $k = 1, \ldots, K$ 而有 $a_{i+k} = b_{j+k}$。

输入包括多个测试用例。每个测试用例的第一行是一个整数 $N$，表示代码的长度（$1 \leq N \leq 10^5$）。接下来两行，每行是一个由 'a' 到 'z' 组成的长度为 $N$ 的字符串，分别表示在两个不同频率下收到的信号。这些信号被认为是无限重复的形式。

对每个测试用例，输出一行，表示两个可能匹配的代码间最长公共子串的长度。 **本翻译由 AI 自动生成**