牛客網-Infinite String Comparision


志のある者は事が成し遂げられ、釜を破って舟を沈め、百二秦関は結局楚に属した.苦心している人は天に負けず、臥薪嘗胆、三千越甲は呉を飲み込むことができる!
Infinite String Comparision
タイトルの説明
For a string xx, Bobo defines x∞ = =xxx…, which is xx repeats for infinite times, resulting in a string of infinite length. Bobo has two strings aa and bb. Find out the result comparing a∞ and b∞ in lexicographical order. You can refer the wiki page for further information of Lexicographical Order.
入力
The input consists of several test cases terminated by end-of-file. The first line of each test case contains a string a, and the second line contains a string b.
  • 1 ≤|a|, |b| ≤ 105
  • a, b consists of lower case letters.
  • The total length of input strings does not exceed 2*106

  • しゅつりょく
    For each test case
  • print “= ” (without quotes) if a∞ =b∞
  • Otherwise, print “< ” if a∞ < b∞
  • or “> ” if a∞> b∞

  • Sample Input
    aa
    b
    zzz
    zz
    aba
    abaa
    

    Sample Output
    <
    =
    >
    

    問題を解く構想の無限循環はずっと循環する必要はなく、無限循環が持つべき性質を体現させるだけでよい.関連先に穴があるにすぎない.最大長の文字列を2倍に広げます.これにより、すべての詳細がこの新しい文字列に反映されます.次に、同じ長さになるまで小さな文字列を拡張します.このとき、2つの新しい文字列がこの無限ループの文字列を表すことができます.
    AC時間~
    #include
    #include
    #include
    #include 
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #pragma warning(disable:4244)
    #define PI 3.141592653589793
    #pragma GCC optimize(2)
    #define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false);
    #define EPS 1.0e-8
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const ll ll_inf = 9223372036854775807;
    const int int_inf = 2147483647;
    const short short_inf = 32767;
    const char char_inf = 127;
    ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
    inline ll read() {
    	ll c = getchar(), Nig = 1, x = 0;
    	while (!isdigit(c) && c != '-')c = getchar();
    	if (c == '-')Nig = -1, c = getchar();
    	while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
    	return Nig * x;
    }
    inline void out(ll a) {
    	if (a < 0)putchar('-'), a = -a;
    	if (a >= 10)out(a / 10);
    	putchar(a % 10 + '0');
    }
    ll phi(ll n)
    {
    	ll ans = n, mark = n;
    	for (ll i = 2; i * i <= mark; i++)
    		if (n % i == 0) { ans = ans * (i - 1) / i; while (n % i == 0)n /= i; }
    	if (n > 1)ans = ans * (n - 1) / n; return ans;
    }
    ll qpow(ll x, ll n, ll mod) {
    	ll res = 1;
    	while (n > 0) {
    		if (n & 1)res = (res * x) % mod;
    		x = (x * x) % mod;
    		n >>= 1;
    	}
    	return res;
    }
    ll mat_mod;
    struct Mat {
    	ll m[10][10];
    };
    Mat Mul(Mat A, Mat B, ll mat_size) {
    	Mat res;
    	memset(res.m, 0, sizeof(res.m));
    	for (int i = 0; i < mat_size; i++)for (int j = 0; j < mat_size; j++)for (int k = 0; k < mat_size; k++)
    		res.m[i][j] = (res.m[i][j] + (A.m[i][k] * B.m[k][j]) % mat_mod) % mat_mod;
    	return res;
    }
    Mat mat_qpow(Mat data, ll power, ll mat_size) {
    	Mat res;
    	memset(res.m, 0, sizeof(res.m));
    	for (int i = 0; i < mat_size; i++)res.m[i][i] = 1;
    	while (power) {
    		if (power & 1)res = Mul(res, data, mat_size);
    		data = Mul(data, data, mat_size), power >>= 1;
    	}
    	return res;
    }
    #define Floyd for(int k = 1; k <= n; k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
    #define read read()
    string c(string b, int n, int l)
    {
    	string res = b;
    	for (int i = 0; i < n; i++)res += b;
    	return res.substr(0, l);
    }
    int main()
    {
    	string a, b;
    	while (cin >> a >> b)
    	{
    		if (a.size() >= b.size())
    		{
    			a = a + a;
    			int la = a.size();
    			int lb = b.size();
    			int k = la / lb;
    			k++;
    			b = c(b, k, la);
    			if (a > b)cout << ">" << endl;
    			else if (a < b)cout << " << endl;
    			else cout << "=" << endl;
    		}
    		else
    		{
    			swap(a, b);
    			a = a + a;
    			int la = a.size();
    			int lb = b.size();
    			int k = la / lb;
    			k++;
    			b = c(b, k, la);
    			if (a > b)cout << " << endl;
    			else if (a < b)cout << ">" << endl;
    			else cout << "=" << endl;
    		}
    	}
    }
    

    By-輪月