Codeforces 311(div 二):E. Ann and Half-Palindrome

Codeforces 311(div 2):E. Ann and Half-Palindrome

题目描述：

给定半回文子串的定义，现给你一个串S和一个整数K，输出S所有子串中且是半回文排名第K的子串，半回文子串按照字典序升序顺序。（len(S) <= 5000）

分析：

首先，定义dp[i][j]表示S[i....j]是否为半回文子串，可以在 Codeforces 311(div 二):E. Ann and Half-Palindrome

的时间内求出所有的状态。现在，需要计算排名第K的半回文子串，我们可以通过将所有的半回文子串插入到一颗字典树中，然后通过先序遍历，找到第K大值，然而，这样做的最坏情况下时间复杂度为 Codeforces 311(div 二):E. Ann and Half-Palindrome

，很显然不可取。我们可以通过利用字符串的公共前缀来优化插入到字典树所消耗的时间，对于串中每一个位置i，以i开头，且是半回文的子串，存在相同的公共前缀，我们只用找到以i开头，最长的半回文子串，然后将其插入到字典树中，在插入过程中，需要判断i到当前点是否为一个半回文子串，并作计数。最后对整颗字典树进行先序遍历，就能找到第K大值，时间复杂度、空间复杂度为 Codeforces 311(div 二):E. Ann and Half-Palindrome

。

#include<bits\stdc++.h>
#define MAX_ASCII 2
using namespace std;
const int N = 5e+3 + 7;
bool dp[N][N];
char str[N];
int dict[N * N][MAX_ASCII + 1], cnt = 1;
//字典树插入
void Insert(const char *s, int L, int R)
{
    int v = 0, i = L;
    while (L <= R)
    {
        if (dict[v][s[L] - 'a'])
            v = dict[v][s[L++] - 'a'];
        else
            v = dict[v][s[L++] - 'a'] = cnt++;
        if (dp[i][L - 1])
            ++dict[v][2];
    }
}
//先序遍历查询第K大值
bool Rank(int v, vector<char> &path, int &k)
{
    k -= dict[v][2];
    if (k <= 0)
    {
        for (auto x : path)
            cout << x;
        cout << endl;
        return true;
    }
    for (int i = 0; i < 2; ++i)
    {
        if (dict[v][i])
        {
            path.push_back((char)(i + 'a'));
            if (Rank(dict[v][i], path, k))
                return true;
            path.pop_back();
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int k, len;
    cin >> str >> k;
    len = strlen(str);
    for (int i = len - 1; i >= 0; --i)
        for (int j = len - 1; j >= i; --j)
            dp[i][j] = i <= j - 4 ? (str[i] == str[j] && dp[i + 2][j - 2]) : str[i] == str[j];
    for (int i = 0; i < len; ++i)
    {
        int j = len - 1;
        for (; j >= i && !dp[i][j]; --j);
        Insert(str, i, j);
    }
    vector<char> path;
    Rank(0, path, k);
    return 0;
}

Codeforces 311(div 二):E. Ann and Half-Palindrome

题目描述：

分析：

相关推荐