虽然这是我的第一篇正式博客…
但是首先：
神金题目名！！！
题目大意：
给定一个小写字母字符串，要求在这个字符串中找到一个后缀，可以给这个后缀每一个字符映射另外一个小写字母（可以为其本身）。但是字母一样映射的那个字母就必须一样。
求出字典序最大的后缀映射。
SAMPLE I/O
I:
O:
测试点限制：
时间限制：
空间限制：
| subtask idx |
|
特殊性质 |
分数 |
|
|
/ |
|
|
|
/ |
|
|
|
字符集为{} |
|
|
|
字符集为{} |
|
|
|
字符集为{} |
|
|
|
/ |
|
思路：
我们可以知道，要使这个映射他的字典序最大，那么第一位必须是，后面就跟着,,…我们可以想到最暴力的做法：
枚举每一个后缀，将这个后缀的第一种字母赋为，第二种字母赋为，一直到最后一个字母，期望得分。
考虑到后面的字符集为{}，可以考虑不是可以映射为就是可以映射为，于是我们就可以找到一个最长的连续的子段，如果有相同的最长的就比较这个字段后面连续的子段的长度，更短的肯定更优，然后第三段连续子段也是更长更优…于是我们就可以找这两个字符串的最长公共前缀来比较，期望得分分。
我们可以沿用之前最长公共前缀的思路，把整个字符串拆成26个0/1字符串，1表示这个位置存在该字母，0表示不存在。从右往左搜索这个字母从左往右第一次出现的位置，之后把出现位置最早的字母赋值为，第二早的赋值为，…之后我们就可以使用二分+哈希求得两个后缀答案的最长公共前缀，然后再看第一次出现差异的地方的字符即可得到顺序。可以通过这些0/1字符串转哈希，来二分差异位置。
复杂度为(其中)。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5+4, A = 29;
typedef unsigned long long ull;
char s[N];
int ord[A], rk[N][A];
int lst[A];
int n, t;
ull has[N][A], mi[N], base = 107;
bool cmp(int x, int y){
return lst[x] < lst[y];
}
ull gethash(int l, int r, int let){
return has[r][let] - has[l-1][let] * mi[r-l+1];
}
void init(){
mi[0] = 1;
for(int i=1;i<N;i++){
mi[i] = (mi[i-1]*base);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>t;
init();
while(t--){
cin>>(s+1);
n=strlen(s+1);
for(int i=0;i<26;i++){
ord[i] = i, lst[i] = n+1;
}
for(int i=n;i>=1;i--){
lst[s[i]-'a'] = i;
sort(ord, ord+26, cmp);
for(int j=0;j<26;j++){
rk[i][ord[j]] = 25-j;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<26;j++){
has[i][j] = has[i-1][j]*base;
}
has[i][s[i]-'a'] ++;
}
int maxid = n;
for(int i=n-1;i>=1;i--){
int l=1, r=n-maxid+1, mid;
while(l<=r){
ull x1, x2;
x1=x2=0;
mid=l+r>>1;
for(int j=0;j<26;j++){
x1 += gethash(i, i+mid-1, j)*rk[i][j];
x2 += gethash(maxid, maxid+mid-1, j)*rk[maxid][j];
}
if(x1==x2) l = mid+1;
else r = mid-1;
}
if(maxid+r>n || rk[i][s[i+r]-'a'] > rk[maxid][s[maxid+r]-'a']) maxid = i;
}
for(int i=maxid;i<=n;i++){
cout<<char(rk[maxid][s[i]-'a']+'a');
}
cout<<"\n";
}
return 0;
}
|
OVER.
