#F Infinite String Comparision# 使用「Z函数」直接将暴力匹配优化成 O(n) 时间
解：比较两个字符串的字典序。使用两根指针总是没错的。
我们知道朴素的解法是：将两个输入字符串都倍增成它们“最小公倍数长度”的字符串，然后用两根指针暴力找第一次不相等的位置，然后比较这个不相等的位置即可知道两个字符串的字典序高低。
这个很顺的思路唯一的缺点是容易超时，超时的原因是「第一次不相等的情况」出现在了很后面的位置，算法主要的时间开销在前面我们比较了大量的相等的情况，直到寻找第一个不相等的情况为止，这个过程因为涉及大量可以被省去的判断。时间复杂度可以达到O(n²)级别，因此，考虑到如何省去这些判断，我们可以想用（扩展kmp）Z函数来优化“打包”这些可以被省去的判断，将算法的时间降低成O(n)级别。
在这里Z数组的计算是一种预处理，就像计算“前缀和数组”一样，由于已经计算好了匹配情况，它让我们能在主要的比较逻辑中，每每比较N个字符的相等情况都只需要O(1)的时间，使用Z数组，朴素算法的时间消耗由 n x n == O(n²)变成了n x 1 == O(n)的级别。而预处理计算Z数组需要的时间复杂度同样也是O(n)级别，因此算法总体时间复杂度为O(n)级别。
参考实现 (Cpp)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 预处理计算Z数组用于优化暴力比较。
vector<int> calcZ(string& a, string& b) {
string s = a + "$" + b;
int n = s.size();
vector<int> Z(n); // Z 数组
int left = -1, right = -1; // [left, right] 标记上一次成功匹配的区间
// 计算Z数组
for (int k = 1; k < n; k++) {
if (k > right) {
left = right = k;
while (right < n && s[right] == s[right - k]) {
right++;
}
Z[k] = right - k;
right--;
} else {
if (k + Z[k - left] - 1 >= right) {
left = k;
while (right < n && s[right] == s[right - k]) {
right++;
}
Z[k] = right - k;
right--;
} else {
Z[k] = Z[k - left];
}
}
}
// 计算完成后，截取出「Z数组的“字符串b部分”」然后返回
return vector<int>(Z.begin() + a.size() + 1, Z.end());
// 也可以选返回整个Z数组，但是主逻辑需要做 + a.size() + 1的小调整，给主逻辑减压，在这里就截取。
// return Z;
}
void solve() {
// 主逻辑
string a, b;
while (cin >> a >> b) {
int flip = 0;
if (a.size() > b.size()) {
swap(a, b);
flip = 1;
} // 交换，让长度更长的字符串是b串。
int n = a.size(), m = b.size();
b += b; // b += b，让字符串 += 自身是一种处理循环字符串的常用技巧，在本题，无穷字符串无限repeat本身，可以被看作循环字符串用这种技巧来处理
vector<int> Z = calcZ(a, b); // 预处理，计算Z函数用于加速判断。
// 比较字典序两步走。
// 一：找到两根指针第一次不相等的位置。
int index = 0;
while (Z[index] == n) {
index = (index + n) % m;
if (index == 0) { // index回到了原位置 = 0，两个字符串比较完了lcm的长度但是还是没有找到不相等的地方。于是两串无穷repeat后的关系是等于。
cout << '=' << '\n';
return;
}
}
// 二。找到了第一个存在不相等的部分，找到后只用O(n)时间即可完成字典序的比较。
if (a < b.substr(index, n)) {
cout << (flip ? '>' : '<') << '\n';
} else {
cout << (flip ? '<' : '>') << '\n';
}
// 注意：「两根指针第一次不相等的位置」是比较字典序的关键。没有题目能够逃得掉，总是可以从这方面考虑。
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
solve();
}
return 0;
}
这题之前：
对于尚未习得“Z函数”的牛友们，这里推荐两处学习资料。
（oi-wiki） https://oi-wiki.org/string/z-func/
京公网安备 11010502036488号