题解 | 对联

从题干里我们看到这句话：

后缀自动机next指针dag图上求sg函数

这个是用来求这道题的方法，只不过需要 t 是 s 的子串而不是子序列

于是把后缀自动机改成子序列自动机这题就解决了，时间复杂度。

#include <iostream>
#include <array>
#include <vector>
using namespace std;

int n;
string s;

vector<array<int, 26>> zdj;
vector<bool> dp;

void Solve() {
    cin >> s;
    n = s.length();
    zdj.resize(n + 1);
    dp.resize(n + 2);
    dp.back() = true;
    zdj[n].fill(n + 1);
    for (int i = n - 1; i > -1; i--) {
        zdj[i] = zdj[i + 1];
        zdj[i][s[i] - 'a'] = i + 1;
    }
    for (int i = n; i > -1; i--) {
        for (const auto& j : zdj[i]) {
            if (!dp[j]) {
                dp[i] = true;
                break;
            }
        }
        // cout << i << ',' << dp[i] << endl;
    }
    cout << (dp[0] ? "kou" : "yukari");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}