1 条题解

  • 2
    @ 2024-7-25 11:56:56
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    const int N = 85;
     
    char s[N], w[N];
    ull a[N], b[N];
    ull base = 131;
     
    ull qpow(ull a, ull b)
    {
        ull ans = 1;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a;
            }
            a = a * a;
            b /= 2;
        }
        return ans;
    }
     
    void hashs(char s[], ull a[])
    {
        int len = strlen(s + 1);
        a[0] = 0;
        for(int i = 1; i <= len; ++i)
        {
            a[i] = a[i - 1] * base + (ull)s[i];
        }
    }
     
    int main()
    {
        scanf("%s", s + 1);
        scanf("%s", w + 1);
        hashs(s, a);
        hashs(w, b);
        int len1 = strlen(s + 1);
        int len2 = strlen(w + 1);
        int x = 0;
        int y = 0;
        for(int i = min(len1, len2); i > 0; --i)
        {
            ull tmp = b[len2] - b[len2 - i] * qpow(base, i);
            if(a[i] == tmp)
            {
                x = i;
                break;
            }
        }
        for(int i = min(len1, len2); i > 0; --i)
        {
            ull tmp = a[len1] - a[len1 - i] * qpow(base, i);
            if(b[i] == tmp)
            {
                y = i;
                break;
            }
        }
        cout<<max(x, y)<<'\n';
        return 0;
    }
    
    • 1

    信息

    ID
    2288
    时间
    1000ms
    内存
    125MiB
    难度
    9
    标签
    递交数
    7
    已通过
    6
    上传者