目录
题面
题解
算法 1
算法 2
算法 3（标答）
代码
算法 1
20pts（by jijidawang）
40pts（by Rolling_Star）
算法 2
算法 3
题面
一个长度为 \(k\) 字符串序列 \(s\) 是好的，当且仅当 \(\forall 1\le i<k\)，有 \(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 可以线性完成，映射可以考虑两种实现方式
| 方式编号 | 表现 \(1\) | 表现 \(2\) | 时间复杂度 |
|---|---|---|---|
| \(1\) | std::map |
平衡树 | \(O(n\log n)\) |
| \(2\) | std::unordered_map |
Hash Table | \(O(n)\) |
期望 \(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<la; i++)
if (a[i] != b[i]) return false;
return true;
}
inline bool chk(string a, string b)
{
bool ans = pure_chk(a, b);
reverse(b.begin(), b.end());
return ans & pure_chk(a, b);
}
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) cin >> s[i];
dp[1] = 1;
for (int i=2; i<=n; i++)
for (int j=1; j<i; j++)
if (chk(s[j], s[i])) dp[i] = max(dp[i], dp[j]+1);
ll ans = 0;
for (int i=1; i<=n; i++) ans = max(ans, dp[i]);
printf("%lld\n", ans);
return 0;
}
40pts（by Rolling_Star）
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<<ans;
}
inline bool check(int x,int y)
{
for(register int i=0;i<s[y].size();++i)
if(s[y][i]!=s[x][i])
return false;
for(register int i=s[x].size()-s[y].size(),j=0;j<s[y].size();++i,++j)
if(s[y][j]!=s[x][i])
return false;
return true;
}
算法 2
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<ll, int> dp;
int main()
{
scanf("%d", &n);
pb[0] = 1;
for (int i=1; i<N; i++) pb[i] = pb[i-1] * base % P;
int ans = 0;
for (int i=1; i<=n; i++)
{
scanf("%s", s+1); int l = strlen(s+1);
ll p=0, ss=0; int H=0;
for (int j=1; j<=l; j++)
{
p = (p*base % P + s[j]) % P;
ss = (ss + s[l-j+1]*pb[j-1] % P) % P;
if (p == ss) H = max(H, dp[p]);
}
dp[p] = max(dp[p], H+1);
ans = max(ans, dp[p]);
} printf("%d\n", ans);
return 0;
}
