2020牛客暑期多校 第一场 F Infinite String Comparision（字符串）

题目传送门

题意： 给你两个字符串，这个字符串可以无限向后延伸，比如"ab"可以延伸为"abababab…"，问你这两个字符串的字典序大小。

思路： 首先我们想到把两个字符串延伸到lcm(lena,lenb)的长度，后面就是重复这一过程了，但是一看数据范围，lena,lenb<=1e5，这样的话，他们的lcm可能是1e10级别的，有限的内存肯定存不下两个这么大的字符串。

那如果两个串直接把短的那个补齐到长的那个去比较，比如"ab",“aba”,第一个串补齐之后，也是"aba",这样并不能判断两个串的大小。

但是我们把长的串延伸一倍，再把短的串补齐。这时候来看两串的大小。如果两个串有直接的大小关系，那么毫无疑问可以直接判断了。如果这时候两个串相等，要么就是原来两个串就相等，要么就是小串是大串的一个小周期，比如ab和abab。

代码：

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define endl '\n'
#define null NULL
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define int long long
#define pii pair<int,int>
#define pdd pair<double,double>
#define ull unsigned long long
#define all(x) x.begin(),x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
return x*f;}
using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f;
const int mod=998244353;
const double eps=1e-7;
const double PI=acos(-1);
void solve(string a,string b,int op)
{
    b+=b;
    string c="";
    int la=a.size();
    for(int i=0;i<b.size();i++)
        c+=a[i%la];
    if(op==1)
    {
        if(c>b)
            cout<<">"<<endl;
        if(c==b)
            cout<<"="<<endl;
        if(c<b)
            cout<<"<"<<endl;
    }
    else
    {
        if(c>b)
            cout<<"<"<<endl;
        if(c==b)
            cout<<"="<<endl;
        if(c<b)
            cout<<">"<<endl;
    }
}
signed main()
{
    string a,b;
    while(cin>>a>>b)
    {
        if(b.size()>a.size())
            solve(a,b,1);
        else
            solve(b,a,2);
    }
}

本文地址：https://blog.csdn.net/Joker_He/article/details/107332760