区块链技术博客
www.b2bchain.cn

模板题(后缀数组的理解) | 错题本的讲解

这篇文章主要介绍了模板题(后缀数组的理解) | 错题本的讲解,通过具体代码讲解7490并且分析了模板题(后缀数组的理解) | 错题本的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了模板题(后缀数组的理解) | 错题本的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7490.html。具体如下:

文章目录

  • 题目
  • 分析
  • 代码

题目

题目描述

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

很不幸的是,小苗在学习 suffix array 时把概念记错了:现在她认为数组 sa 的互逆数组是原串

SS

,然而 sa 的互逆数组应该是 rank : (。

为了帮助小苗同学,现给定一字符串

SS

,请你判断是否存在

TT

,使得

SS

TT

sa 数组相同,且

TT

的字典序比

SS

小。

具体来说,sa 是一个一维数组,它保存从

11

nn

的某个排列 ,并且对于

1i<n1 leq i < n

,保证

S[sain]S[sa_idots n]

的字典序小于

S[sai+1n]S[sa_{i+1}dots n]

的字典序。

输入格式
一行一个字符串

SS

。保证仅由小写字母构成。

输出格式
如果存在相应的

TT

,则输出 Exists;否则输出 Does not exist

你需要保证对应的

TT

也由小写字母构成。

输入输出样例

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

说明/提示

SS

的长度为

nn

,对于所有子任务,有

n50n leq 50

  • subtask 1 (20 points):
    n3n leq 3

  • subtask 2 (20 points):
    n7n leq 7

  • subtask 3 (30 points):
    SS

    仅包含 ab 两种字符;

  • subtask 4 (30 points):无任何特殊限制。

分析

性质是,

TT

SS

最多相差一个字符。因此我们枚举

SS

中的一个不为 a 的字符并将其减一得到

TT’

,再判断

SS

TT’

sa 是否相同即可。

证明:我们只需证明,如果

SS

改变一个字符无法做到 sa 相同,那么改变更多的也不能做到 sa 相同。考虑我们已知

SS

sa 数组

sasa

,则 rank 数组

rkrk

也可以得到。对于任意一个

1i<n1 leq i < n

,假设越界的地方

rkrk

00

,有

S[sai]<S[sai+1]  (S[sai]=S[sai+1]  rk[sai+1]<rk[sai+1+1])S[sa_i] < S[sa_{i + 1}] 或 (S[sa_i]=S[sa_{i + 1}] 且 rk[sa_i + 1] < rk[sa_{i + 1} + 1])

于是有

{S[sai]<S[sai+1],(rk[sai+1]rk[sai+1+1])S[sai]S[sai+1],(rk[sai+1]<rk[sai+1+1])begin{cases} S[sa_i] < S[sa_{i + 1}], & (rk[sa_i + 1] geq rk[sa_{i + 1} + 1]) \ S[sa_i] leq S[sa_{i + 1}], & (rk[sa_i + 1] < rk[sa_{i + 1} + 1])end{cases}

于是我们可以根据

SS

rkrk

确定出以

TT

nn

个字符为未知数的

n1n – 1

个不等式,如果

TT

的每个字符都满足这个不等式,则

TT

sa

SS

sa 相等。同时可以看出,更改一个字符只会影响两个不等式,更改更多的字符会影响更多的不等式,所以显然更改一个字符是“最有可能”使

TT

SS

sa 相同的。

这道题可以暴力求 sa
当然,有了上面那个不等式我们也可以不用每次对

TT

都重新算 sa,直接判断会影响到的那个不等式即可。


这个

nn

元的不等式组感觉会很有用,比如说可以根据一个 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; } 

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

本文地址https://www.b2bchain.cn/7490.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 模板题(后缀数组的理解) | 错题本的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们