题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>

using namespace std;

typedef unsigned long long ULL;
const int N = 10010, P = 131;
ULL h[N], p[N];
bool f[N];
char str[N], word[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
    cin >> str + 1;
    int n = strlen(str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    unordered_set<ULL> hash;
    while(cin >> word)
    {
        ULL t = 0;
        for (int i = 0; word[i]; i ++) t = t * P + word[i];
        hash.insert(t);
    }

    f[0] = true;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j; j --)
        {
            if (f[j - 1] && hash.count(get(j, i)))
            {
                f[i] = true;
                break;
            }
        }
    if (f[n]) puts("True");
    else puts("False");
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla