• 题面
• 题解
  • 算法 1
  • 算法 2
  • 算法 3（标答）
• 代码
  • 算法 1
    • 20pts（by jijidawang）
    • 40pts（by Rolling_Star）
  • 算法 2
  • 算法 3

题面

一个长度为 \(k\) 字符串序列 \(s\) 是好的，当且仅当 \(\forall 1\le i，有 \(B_i\) 既是 \(B_{i+1}\) 的前缀，又是 \(B_{i+1}\) 的后缀 .

给一个字符串序列 \(A\)，求其最长好子序列 .

数据范围：\(\displaystyle \sum_k |A_k|\le 2\times 10^6\)

时限 \(2\ \rm s\)，空限 \(512\rm\ MB\) .

题解

算法 1

考虑 dp .

令 \(dp_i\) 表示以 \(A_i\) 结尾的最长好序列，于是可以暴力转移 .

时间复杂度 \(O(n^3)\)，期望 \(20\sim 40pts\) .

算法 2

考虑加速算法 \(1\) 中转移过程 .

字符串 Hash 处理每个子串的 border，同时构建映射 \(\mathrm M:\,border\to dp\) .

一轮 dp 可以线性完成，映射可以考虑两种实现方式

期望 \(100pts\) .

算法 3（标答）

记 \(\overline s\) 为 \(s\) 逆序排成的字符串 .

于是 \(s\) 是 \(t\) 的后缀等价于 \(\overline s\) 是 \(\overline t\) 的前缀 .

现在我们有两个前缀关系，建 Trie 树并且在 Trie 树上 dp 即可 .

期望 \(100pts\) .

代码

算法 1

20pts（by jijidawang）

using namespace std;
typedef long long ll;
const int N = 1e6 + 500;
int n;
ll p, dp[N];
string s[N];
inline bool pure_chk(string a, string b)
{
	int la = a.length(), lb = b.length();
	if (la > lb) return false;
	for (int i=0; i> s[i];
	dp[1] = 1;
	for (int i=2; i<=n; i++)
		for (int j=1; j

using namespace std;

int n,dp[2000001];
string s[2000001];
bool flag;
inline bool check(int x,int y);

int main()
{
    cin>>n;
    for(register int i=1;i<=n;i++)
        cin>>s[i];
    int ans=0;
    dp[1]=1;
    for(register int i=2;i<=n;++i)
    {
        dp[i]=1;
        for(register int j=1;j<=i-1;++j)
            if(s[i].size()>=s[j].size())
                if(check(i,j))
                    dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    cout<

using namespace std;
const int N = 1e6 + 500;
typedef long long ll;
typedef char str[N];
const ll P = 1e9+7, base = 131;
int n;
ll pb[N];
str s;
map dp;
int main()
{
	scanf("%d", &n);
	pb[0] = 1;
	for (int i=1; i