F - Infinite String Comparision
F 暴力莽签到题
题意
两个串s, t, 试比较和
的大小关系
思路
根据Periodicity Lemma可知，若在范围内没有适配，那么
和
相等，否则按照字典序关系比较。
代码
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int cmp(const string& s, const string& t) {
const size_t slen = s.length(), tlen = t.length();
const size_t len = slen + tlen - __gcd(slen, tlen);
for (int i = 0; i < len; ++i) {
if (s[i % slen] < t[i % tlen]) return 0;
else if (s[i % slen] > t[i % tlen]) return 2;
}
return 1;
}
int main() {
string s, t;
while(cin >> s >> t) {
cout << "<=>"[cmp(s, t)] << "\n";
}
return 0;
}
