题目描述

For a string \(x\) ,Bobo define \(x^{\infty}\) =xxx,,,which is x repeats for infinite times ,resulting in a string of infinite length. Bobo has two strings a and b. Find out the result comparing \(a^{\infty}\) and \(b^{\infty}\) in lexicographical order. You can refer the wiki page further information of Lexicographical Order.

输入描述

The input consist of several test cases terminated by end - of - file .

The first line of each test cases contains a string a,and the second line contains a string b

• 1≤|a|, |b|≤\(10^{5}\)
• a, b consists of lower case letters
• The total length of input strings does not exceed 2 x \(10^{6}\)

输出描述

For each test cases , print "=" ,if \(a^{\infty}\) = \(b^{\infty}\) , otherwise, print "<",if \(a^{\infty}\) < \(b^{\infty}\) ,or ">",if \(a^{\infty}\) > \(b^{\infty}\)

示例一

输入

aa

b

zzz

zz

aba

abaa

输出

<
=
>

题解

#include <cstdio>
#include <cstring>

static const int N = 100000;

//求最大公约数 
template <typename T> 
T gcd(T a, T b){ 
	return b ? gcd(b, a % b) : a; 
}
int main() {
	//存放两个字符串 
 	static char a[N + 1], b[N + 1];
 	//读到EOF为止 
  	while (scanf("%s%s", a, b) == 2) {
  	 	//取出两个串的长度 
	    int alen = strlen(a);
	    int blen = strlen(b);
	    //如果超出maxlen还相等，那么这两个字符串相等 
	    int maxlen = alen + blen - gcd(alen, blen);
	    char result = '=';
	    //开始遍历，只要出现字符不相等的情况，就跳出，并输出大于小于号 
	    for (int i = 0; i < maxlen && result == '='; ++i) {
	      char ai = a[i % alen];
	      char bi = b[i % blen];
	      if (ai != bi) {
	        result = ai < bi ? '<' : '>';
	      }
    }
    //输出结果 
    printf("%c\n", result);
  }
}

关于周期性引理，定理内容：

假设一个字符串 有循环节 和 并且满足 ，那么 也是一个循环节。

设两个字符串为a，b在本题的标程中，每两个字符串的匹配次数是\(|a|+|b|-gcd（a，b）\)，如果超出这个次数，就不用匹配了，直接认定两个字符串相等。但我觉得，这样有些不妥当，因为这个定理中说，满足\(p+q≤|S|+gcd(p,q)\)的话，那么\(gcd(p,q)\)是一个循环节，也就是说，\(p+q≤|S|+gcd(p,q)\)并不恒成立，那么为什么要以这个为匹配次数最大值？

这道题数据太水，直接把字符串首尾相接，也就是a+=a,b+=b,然后循环次数变成两个字符串长度最大值，然后直接匹配就行了。