【2020牛客多校一：字元串】F ：Infinite String Comparision

入口

【難度】

1/10

簽到題

【題意】

給定一個字元串x，定義 x ∞ = x x x ⋯ \pmb{x^\infty=xxx\cdots} x∞=xxx⋯x∞=xxx⋯x∞=xxx⋯

你有兩個字元串a,b

請你比較 a ∞ 和 b ∞ a^\infty和b^\infty a∞和b∞字典序的大小

【資料範圍】

1 ≤ ∣ a ∣ , ∣ b ∣ ≤ 1 0 5 1\le|a|,|b|\le10^5 1≤∣a∣,∣b∣≤105

【樣例輸入】

aa

b

zzz

zz

aba

abaa

【樣例輸出】

<

=

>

【思路】

根據 P e r i o d i c i t y   L e m m a \pmb{Periodicity\ Lemma} Periodicity Lemma​Periodicity Lemma​​Periodicity Lemma,我們隻要讓字元串 a a a與 b b b變成串 a a aa aa與串 b b bb bb

然後取 max ⁡ ( ∣ a a ∣ , ∣ b b ∣ ) \max(|aa|,|bb|) max(∣aa∣,∣bb∣)作為比較的次數。

每次比較後兩個指針向後移位，若移動到末尾則即變為開頭指針，用取模操作模拟。

然後即可從左到右比較字典序大小。若還沒比出大小，則兩個無窮字元串字典序相同。

【AC核心代碼】

時間複雜度O( 2 max ⁡ ( ∣ a ∣ , ∣ b ∣ ) 2\max(|a|,|b|) 2max(∣a∣,∣b∣))

空間複雜度O(|a|+|b|)

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
string s1,s2;
int main()
{
    ///IOS;
    while(cin >> s1 >> s2){
        int pd=0;
        int ed1=s1.size();
        int ed2=s2.size();
        int ed = 2*max(ed1,ed2);
        for(int i=0;i<ed;++i){
            if(s1[i%ed1]>s2[i%ed2]){
                pd = 1;
                break;
            }
            if(s1[i%ed1]<s2[i%ed2]){
                pd=-1;
                break;
            }
        }
        if(pd==0)cout << "=" << endl;
        else if(pd==1)cout << ">" << endl;
        else cout << "<" << endl;
    }
    return 0;
}