1 条题解

  • 0
    @ 2023-3-8 16:22:00
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1000000;
    string s;
    // Hash
    const long long MOD = 1000000007;
    const int P = 29;
    long long myHash[MAXN + 5];
    long long powP[MAXN + 5];
    // 初始化 s[1]~s[n] 的前缀哈希
    void initHash(int n)
    {
        powP[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            myHash[i] = (myHash[i - 1] * P + s[i] - 'a' + 1) % MOD;
            powP[i] = powP[i - 1] * P % MOD;
        }
        powP[n + 1] = powP[n] * P % MOD;
    }
    // 获取 s[l]~s[r] 的哈希值
    int getHash(int l, int r)
    {
    
        return (myHash[r] - myHash[l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        while (cin >> s)
        {
            if (s == ".")
                break;
            int n = s.length();
            s = "^" + s + "$";
            initHash(n);
            int ans = -1;
            int i;
            // 循环节长度 len: 1~sqrt(n)
            for (i = 1; i * i <= n; i++)
            {
                if (n % i != 0)
                    continue;
                int len = i;
                if (getHash(1, n - len) == getHash(len + 1, n))
                {
                    ans = n / len;
                    break;
                }
            }
            if (ans != -1)
            {
                cout << ans << "\n";
                continue;
            }
            // len: sqrt(n)~n
            for (; i >= 1; i--)
            {
                if (n % i != 0)
                    continue;
                int len = n / i;
                if (getHash(1, n - len) == getHash(len + 1, n))
                {
                    ans = n / len;
                    break;
                }
            }
            cout << ans << "\n";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    677
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    69
    已通过
    20
    上传者