字符串后缀子串的刻板度：动态规划求解

我们称长度为n的字符串S为由n个在0∼m−1内的整数构成的数列，我们称该数组中的各个元素为其的各个字符，依次记为S0,S1,…,Sn−1。

对一个字符串S，我们称其子串Sl∼r为Sl,Sl+1,…,Sr这些字符顺次拼接起来形成的字符串。

我们称两个字符串相等当且仅当其长度相等且各字符顺次相同。即，对于字符串A,B，我们称A=B当且仅当n=m且∀0≤j<n,Aj=Bj。

对于一个长为n的字符串S，我们称长度b为其的一个Border长度，当且仅当1≤b≤n且S0∼b−1=Sn−b∼n−1。在此基础上，我们称子串S0∼b−1为其的一个Border。

我们称字符串A对B的相对代价，为A的Border中不是B的Border的字符串的长度之和。

我们称字符串A和B的绝对代价，为A对B的相对代价和B对A的相对代价中较大的一个，记为f(A,B)。

我们称长度为n的字符串S的刻板度为其每两个后缀的绝对代价之和，也即 g(S)=∑i=0n−1∑j=i+1n−1f(Si∼n−1,Sj∼n−1)

现在给你一个长度为n的字符串S，你要对其最长的c个后缀子串S'，求出S'的刻板度；即，你需要对每个0≤l<c求出 hl(S)=g(Sl∼n−1)=∑i=ln−1∑j=i+1n−1f(Si∼n−1,Sj∼n−1)

由于答案可能很大，只用输出对2^64取模的结果。

输入格式

第一行四个整数n,m,c,o，其中o将指示更多特殊性质，请参见「数据范围与提示」一节的描述。

接下来一行n个整数，依次表示S0,S1,S2,…,Sn−1。

输出格式

一行c个整数，依次表示h0(S) mod 2^64,h1(S) mod 2^64,h2(S) mod 2^64,…,hc−1(S) mod 2^64。

使用c++14解决问题并说明思路内容：

解题思路：

首先，我们需要计算字符串S的每个后缀子串的绝对代价。
对于每个后缀子串Sl∼n−1，我们需要计算其与所有后缀子串Sm∼n−1 (l≤m<n)的相对代价。
我们可以使用动态规划来解决问题。我们定义dp[i]为以Si∼n−1为后缀的后缀子串的绝对代价。
对于每个dp[i]，我们需要遍历dp[i+1], dp[i+2], ..., dp[n-1]来计算其与后缀子串的相对代价。
我们可以使用一个辅助数组border来记录每个dp[i]的Border长度。border[i]表示以Si∼n−1为后缀的后缀子串的Border长度。
根据Border的定义，我们可以通过比较Si与Sn−border[i]的前border[i]个字符是否相等来计算border[i]。
计算相对代价时，我们只需要计算border[i]以外的字符的长度。
最后，我们需要遍历所有的dp[i]，计算其与后缀子串的相对代价，然后取最大值作为答案。

代码实现：

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

vector<long long> solve(string S, int n, int m, int c) {
    vector<long long> dp(n);
    vector<int> border(n);

    for (int i = n - 2; i >= 0; i--) {
        if (S[i] == S[n - 1]) {
            border[i] = border[i+1] + 1;
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        dp[i] = dp[i+1];
        if (border[i] > 0) {
            dp[i] += border[i];
        }
    }

    vector<long long> result;
    for (int l = 0; l < c; l++) {
        long long sum = 0;
        for (int i = l; i < n - 1; i++) {
            sum += dp[i+1];
            if (border[i] > 0) {
                sum -= border[i];
            }
        }
        result.push_back(sum % 18446744073709551616);
    }

    return result;
}

int main() {
    int n, m, c, o;
    cin >> n >> m >> c >> o;

    string S;
    cin >> S;

    vector<long long> result = solve(S, n, m, c);

    for (long long ans : result) {
        cout << ans << ' ';
    }
    cout << endl;

    return 0;
}

时间复杂度分析：

构建border数组的时间复杂度为O(n)，计算dp数组的时间复杂度为O(n)，遍历dp数组计算相对代价的时间复杂度为O(n)，总时间复杂度为O(n)。