(旧存档) 牛客多校第一场-F题

F 暴力莽签到题

题意

两个串s, t, 试比较$s^{\infty}$和$t^{\infty}$的大小关系

思路

根据 Periodicity Lemma 可知，若在$|S|+|T|-gcd(|S|, |T|)$范围内没有适配，那么$s^{\infty}$和$t^{\infty}$相等，否则按照字典序关系比较。

代码

#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;
}