rt

下述算法的复杂度是 $\Omicron(L^2)$ 的,但是借助O2可以卡过去

hack的大概思路是让拉长字符串长度和结果串长度,同时在前几位出现尽可能多样的字符.

附代码:

#include <iostream>
#include <string>

using namespace std;
int pi[1000005], len, cnt;
bool use[30];
string s, sub;

int main()
{
    ios::sync_with_stdio(false);
    cin >> len >> s;
    for (int i = 0; i < len; i++)
        if (!use[s[i] - 'a'])
        {
            use[s[i] - 'a'] = true;
            cnt++;
        }
    // 保证sub串中出现所有s中出现的字符
    for (int i = 0; i < len && cnt; i++)
    {
        sub += s[i];
        if (use[s[i] - 'a'])
        {
            use[s[i] - 'a'] = false;
            cnt--;
        }
    }
    cnt = sub.length();
    sub.erase(cnt - 1);
    // 穷举匹配
    for (int sub_len = cnt; sub_len <= len; sub_len++)
    {
        sub += s[sub_len - 1];
        bool find = true;
        // 能够整串匹配的部分
        for (int k = 2; find && k <= len / sub_len; k++)
            for (int j = 0; j < sub_len; j++)
                if (s[(k - 1) * sub_len + j] != sub[j])
                {
                    find = false;
                    break;
                }
        // 剩余部分
        for (int i = len / sub_len * sub_len; i < len; i++)
            if (s[i] != sub[i - len / sub_len * sub_len])
            {
                find = false;
                break;
            }
        if (find)
        {
            cout << sub_len << endl;
            break;
        }
    }
    return 0;
}
···