题目

题目描述

小苗在学习字符串。在以下说明中，我们仅考虑由小写字母构成的串。

很不幸的是，小苗在学习 suffix array 时把概念记错了：现在她认为数组 sa 的互逆数组是原串 $S$，然而 sa 的互逆数组应该是 rank : (。

为了帮助小苗同学，现给定一字符串 $S$ ，请你判断是否存在 $T$ ，使得 $S$ 与 $T$ 的 sa 数组相同，且 $T$ 的字典序比 $S$ 小。

具体来说，sa 是一个一维数组，它保存从 $1$ 到 $n$ 的某个排列 ，并且对于 $1\le i<n$，保证 $S[s{a}_i\dots n]$ 的字典序小于 $S[s{a}_{i+1}\dots n]$ 的字典序。

输入格式
一行一个字符串 $S$ 。保证仅由小写字母构成。

输出格式
如果存在相应的 $T$ ，则输出 Exists；否则输出 Does not exist。

你需要保证对应的 $T$ 也由小写字母构成。

输入输出样例

• 输入 #1
  abc
  输出 #1
  Exists
• 输入 #2
  aba
  输出 #2
  Does not exist
• 输入 #3
  examplesareveryweakthinktwicebeforesubmit
  输出 #3
  Exists
• 输入 #4
  nefbgnpckkldfmadajifplcgngooiamrdiahkdgqjjbac
  输出 #4
  Does not exist
• 输入 #5
  bbnelcjqcigsdajojgerfegafcvjffcrblpfbtmbocc
  输出 #5
  Exists

说明/提示
设 $S$ 的长度为 $n$，对于所有子任务，有 $n\le 50$。

• subtask 1 (20 points)：$n\le 3$；
• subtask 2 (20 points)：$n\le 7$；
• subtask 3 (30 points)：$S$ 仅包含 a、b 两种字符；
• subtask 4 (30 points)：无任何特殊限制。

分析

性质是，$T$ 与 $S$ 最多相差一个字符。因此我们枚举 $S$ 中的一个不为 a 的字符并将其减一得到 $T^{\prime }$，再判断 $S$ 与 $T^{\prime }$ 的 sa 是否相同即可。

证明：我们只需证明，如果 $S$ 改变一个字符无法做到 sa 相同，那么改变更多的也不能做到 sa 相同。考虑我们已知 $S$ 的 sa 数组 $sa$，则 rank 数组 $rk$ 也可以得到。对于任意一个 $1\le i<n$，假设越界的地方 $rk$ 为 $0$，有 $$S[s{a}_i]<S[s{a}_{i+1}]或(S[s{a}_i]=S[s{a}_{i+1}]且rk[s{a}_i+1]<rk[s{a}_{i+1}+1])$$ 于是有 $$\{\begin{array}{ll}S[s{a}_i]<S[s{a}_{i+1}],& (rk[s{a}_i+1]\ge rk[s{a}_{i+1}+1])\\ S[s{a}_i]\le S[s{a}_{i+1}],& (rk[s{a}_i+1]<rk[s{a}_{i+1}+1])\end{array}$$ 于是我们可以根据 $S$ 的 $rk$ 确定出以 $T$ 的 $n$ 个字符为未知数的 $n-1$ 个不等式，如果 $T$ 的每个字符都满足这个不等式，则 $T$ 的 sa 与 $S$ 的 sa 相等。同时可以看出，更改一个字符只会影响两个不等式，更改更多的字符会影响更多的不等式，所以显然更改一个字符是“最有可能”使 $T$ 与 $S$ 的 sa 相同的。

这道题可以暴力求 sa。
当然，有了上面那个不等式我们也可以不用每次对 $T$ 都重新算 sa，直接判断会影响到的那个不等式即可。

这个 $n$ 元的不等式组感觉会很有用，比如说可以根据一个 sa 数组求出字典序最小的原串。

代码

纯暴力：

#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
const int MAXN = 50;
int N;
char S[MAXN + 5], T[MAXN + 5];
int SA1[MAXN + 5], SA2[MAXN + 5];
std::vector<std::string> Suf;
void GetSA(char *str, int *sa) {
Suf.clear();
for (int i = 1; i <= N; i++) {
std::string tmp;
for (int j = i; j <= N; j++)
tmp += str[j];
Suf.push_back(tmp);
}
std::sort(Suf.begin(), Suf.end());
for (int i = 0; i < int(Suf.size()); i++)
sa[i + 1] = N - Suf[i].length() + 1;
}
int main() {
scanf("%s", S + 1);
N = strlen(S + 1);
GetSA(S, SA1);
memcpy(T, S, sizeof S);
for (int i = 1; i <= N; i++) {
if (S[i] != 'a') {
T[i] = S[i] - 1;
GetSA(T, SA2);
bool res = true;
for (int j = 1; j <= N && res; j++)
if (SA1[j] != SA2[j])
res = false;
if (res)
return puts("Exists"), 0;
T[i] = S[i];
}
}
puts("Does not exist");
return 0;
}

半暴力：

#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
const int MAXN = 50;
int N;
bool P[MAXN + 5];
char S[MAXN + 5];
int SA[MAXN + 5], Rank[MAXN + 5];
std::vector<std::string> Suf;
void GetSA(char *str, int *sa) {
Suf.clear();
for (int i = 1; i <= N; i++) {
std::string tmp;
for (int j = i; j <= N; j++)
tmp += str[j];
Suf.push_back(tmp);
}
std::sort(Suf.begin(), Suf.end());
for (int i = 0; i < int(Suf.size()); i++)
sa[i + 1] = N - Suf[i].length() + 1;
}
int main() {
scanf("%s", S + 1);
N = strlen(S + 1);
GetSA(S, SA);
for (int i = 1; i <= N; i++)
Rank[SA[i]] = i;
for (int i = 1; i < N; i++)
if (Rank[SA[i] + 1] >= Rank[SA[i + 1] + 1]) // S[SA[i]] < S[SA[i + 1]]
P[SA[i]] = true;
for (int i = 1; i <= N; i++) {
if (S[i] != 'a') {
int j = SA[Rank[i] - 1];
if ((P[j] && S[j] < S[i] - 1) || (!P[j] && S[j] < S[i])) {
puts("Exists");
return 0;
}
}
}
puts("Does not exist");
return 0;
}

然而两个时间只差一毫秒 = =

最后

以上就是贤惠蓝天为你收集整理的模板题（后缀数组的理解） | 错题本题目分析代码的全部内容，希望文章能够帮你解决模板题（后缀数组的理解） | 错题本题目分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。