题目描述

难度分:$1800$

输入长度在$[5,10^4]$的字符串$s$，只包含小写英文字母。

$s$是以如下方式生成的：

1. 首先，找一个长度$\geq 5$的词根。
2. 然后在这个词根的右边，添加若干长为$2$或$3$的后缀。

要求：不能连续添加两个相同的后缀。

输出所有可能的后缀有多少个，以及按字典序升序输出所有可能的后缀。

输入样例$1$

abacabaca

输出样例$1$

3
aca
ba
ca

输入样例$2$

abaca

输出样例$2$

0

算法

记忆化搜索

让字符串$s$的下标从$0$开始取，用记忆化搜索来实现这个DP。

状态定义

$dp[i][pre]$表示如果前缀$[0,i)$是原串，上一次追加的$2$到$3$长度的子串为$pre$的情况下，后缀$[i,n)$是追加$2$或$3$长度的子串构建出来的，这是否可以做到？

状态转移

$base$ $case$：$i=n$说明刚好前面刚好由长度为$2$或$3$的串构建出了后缀，返回true。$i=n-1$表示剩下最后一个字符落单，没办法凑长度为$2$或$3$的串，构建失败返回false。

否则看看$s[i…i+1] \neq pre$和$s[i…i+2] \neq pre$能否成立，从而判断当前能否追加一个合法的串。状态转移方程为$dp[i][pre]=dp[i+2][s[i…i+1]] \lor dp[i+3][s[i…i+2]]$。

如果$dp[i+2][s[i…i+1]]=$true，说明$s[i…i+1]$是合理的，追加到答案集合（有序集合）中。如果$dp[i+3][s[i…i+2]]=$true，说明$s[i…i+2]$是合理的，追加到答案集合中。$dfs$结束之后，把答案集合中的字符串打印一遍既可以了。

复杂度分析

时间复杂度

不太确定$pre$是个什么量级，但造了些$case$打了下表，发现没几百个。粗略估计状态数量应该是$O(\alpha \times n)$，$\alpha$应该是一个和字符集大小$\Sigma$有关的量。而单次转移的时间复杂度为$O(1)$，但在将当前子串插入到有序集合中去的时候，时间复杂度为$O(log_2n)$，因此估计总的时间复杂度就是$O(\alpha \times nlog_2n)$。

空间复杂度

空间消耗的瓶颈就是DP矩阵，也就是状态数量，答案集合中元素的数量应该和状态数量是同一级别，额外空间复杂度大概为$O(\alpha \times n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

void solve(string& s) {
    int n = s.size();
    set<string> ans;
    unordered_map<string, bool> dp[n + 1];
    function<bool(int, string& pre)> dfs = [&](int i, string& pre) {
        if(i == n) return true;
        if(i == n - 1) return false;
        if(dp[i].count(pre)) return dp[i][pre];
        string cur;
        cur.push_back(s[i]);
        cur.push_back(s[i + 1]);
        bool ok = pre == "*"? dfs(i + 1, pre): false;
        if(cur != pre) {
            if(dfs(i + 2, cur)) {
                ans.insert(cur);
                ok = true;
            }
        }
        if(i + 2 < n) {
            cur.clear();
            cur.push_back(s[i]);
            cur.push_back(s[i + 1]);
            cur.push_back(s[i + 2]);
            if(cur != pre) {
                if(dfs(i + 3, cur)) {
                    ans.insert(cur);
                    ok = true;
                }
            }
        }
        return dp[i][pre] = ok;
    };
    string start = "*";
    dfs(5, start);
    cout << ans.size() << endl;
    for(string res: ans) {
        cout << res << endl;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    if(n <= 6) {
        cout << "0\n";
    }else if(n == 7) {
        cout << "1\n";
        cout << s.substr(5, 2) << endl;
    }else {
        solve(s);
    }
    return 0;
}