中规中矩的字符串题.
题意
给出一个字符串\(s\), 你可以选取\(s\)的任意子串将其翻转得到\(s'\), 该操作最多进行一次. 求字典序最小的\(s'\).
\(|s| \leq 10^5, \sum |s| \leq 1.5 \cdot 10 ^ 6\)
题解
以下字符串的下标均从\(0\)开始. \(lcp(s,t)\)代表\(s\)和\(t\)的最长公共前缀. \(rev(s)\)表示将\(s\)翻转后的字符串.
part 1：优化做法
设\(n = |s|\), 朴素的暴力需要至少\(O(n^2)\)来枚举翻转子串的两个端点\(L,R\). 我们需要想办法固定住其中的一个端点.
首先尝试放开限制, 把翻转变成任意排列. 这样将\(s\)排序后得到的\(s'\)一定是最优的. 记这样的\(s'\)为\(t\).
回到原题, 容易看出, \(s\)和\(t\)的最长公共前缀部分无论我们如何操作都不可能再让字典序变小, 而在这之后的部分是有可能减小字典序的. 且因为字典序的性质(比较第一个不相同的字符), 我们必须尝试让\(s'\)和\(t\)不同的第一个字符最小. 因此\(L = lcp(s,t)\).
part 2：快速比较两字符串大小
设当前的最优答案为\(ans\), 在固定了\(L\)之后, 只需\(O(n)\)枚举\(R\), 并快速比较\(ans\)和\(s'\)的大小即可. 这里可以用\(lcp\)来比较两个字符串的大小.
设需要比较\(A = s[a...b]\)和\(B = s[c...d]\)的关系. 若\(lcp(a,c) \ge \min(|A|,|B|)\),则\(A < B\)等价于\(|A| < |B|\) 否则, \(A < B\)等价于\(rank[a] < rank[c]\)
1
2
3
4
5
6
7
8
| int CompString(int s1,int len1,int s2,int len2){
int tlcp = (s1 == s2?min(len1,len2):LCP(s1,s2));
if(tlcp >= min(len1,len2)){
return len1 < len2?-1:(len1 == len2?0:1);
}
else return c[s1] < c[s2]?-1:(c[s1] == c[s2]?0:1);
}
|
注意: 可以只用\(lcp\)来比较字符串大小(这样就可以用hash等方法来求\(lcp\)而不用写SA). 只要把上面的第6行替换为
1
| else return s[s1 + tlcp] < s[s2 + tlcp]?-1:(s[s1 + tlcp] == s[s2 + tlcp]?0:1);
|
即可.
part 3 ：细节部分
首先将整个翻转后的\(s\)拼接在原字符串后, 中间用特殊字符隔开, 例如u = s + "$" + rev(s). 再使用后缀数组处理\(u\). 这样在原串中位置为\(i\)的字符, 在反串中的位置就是\(2*n - i\).
假设当前枚举到\(R\), 最优答案为\(R'\), 如下图:
我们需要比较的是\(s[L,R'-1] + rev(s[R',R])\)和\(rev(s[L,R])\)的大小, 如果后者更小则更新答案. 为了方便比较, 可以将每段字符划分成AB两段:
现在需要比较的就是\(rev(A_1) + B_1\)和\(rev(A_2) + rev(B_2)\)的大小. 由于A, B长度分别相等, 可以用part2的方法分别比较\(rev(A_1)\)与\(rev(A_2)\), \(B_1\)与\(rev(B_2)\)的大小
每段的(起始位置,长度)可以通过简单推导得到:
\(rev(A_1)\): \((2*n - R',R' - L + 1)\)
\(rev(A2)\): \((2*n - R,R - L + 1)\)
\(B_1\): \((R' + 1,i - R')\)
\(rev(B_2)\): \((2*n - R + R' - L + 1,i - R')\)
其他细节见代码. 时间复杂度\(O(n \log n)\). jls好像有\(O(n)\)做法, 有没有好哥哥教教QAQ
代码
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10;
const int maxm = maxn*2;
const int p = 1e9+7;
ll Pow(ll x,ll d,ll p){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2,p);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
struct Node{
int a,b;
Node(int a = 0,int b = 0):a(a),b(b){}
bool operator < (const Node & x){
return a == x.a?b < x.b:a < x.a;
}
};
int lcp[maxn],ST[maxn][20];
struct SA{
string s;
int n;
vector<int>sa,c;
SA(string s = ""):s(s){
sa.clear(),c.clear();
s += '$';
n = s.size();
sa.assign(n,0);
c.assign(n,0);
}
void count_sort(vector<int> & sa,vector<int> & c){
vector<int>pos(n),cnt(n),sa_new(n);
for(int x:c)cnt[x]++;
for(int i = 1;i < n;i++)pos[i] = pos[i-1] + cnt[i-1];
for(int x:sa){
int d = c[x];
sa_new[pos[d]] = x;
pos[d]++;
}
sa = sa_new;
}
void cal(){
{
vector<Node>A(n);
for(int i = 0;i < n;i++)A[i] = Node(s[i],i);
sort(A.begin(),A.end());
for(int i = 0;i < n;i++)sa[i] = A[i].b;
c[sa[0]] = 0;
for(int i = 1;i < n;i++){
c[sa[i]] = c[sa[i-1]] + (A[i].a != A[i-1].a);
}
}
int k = 0;
while((1<<k) < n){
for(int i = 0;i < n;i++)sa[i] = (sa[i] - (1<<k) + n)%n;
count_sort(sa,c);
vector<int>c_new(n);
c_new[sa[0]] = 0;
for(int i = 1;i < n;i++){
pair<int,int>now = {c[sa[i]],c[(sa[i] + (1<<k)) % n]};
pair<int,int>prev = {c[sa[i-1]],c[(sa[i-1] + (1<<k)) % n]};
c_new[sa[i]] = c_new[sa[i-1]] + (now != prev);
}
k++;
c = c_new;
}
}
void ST_init(){
for(int i = 1;i <= n;i++)ST[i][0] = lcp[i];
for(int j = 1;(1<<j) <= n;j++)
for(int i = 1;i + (1<<j) -1 <= n;i++)
ST[i][j] = min(ST[i][j - 1],ST[i + (1<<(j - 1))][j - 1]);
}
int LCP(int L,int R){
L = c[L],R = c[R];
if(L > R)swap(L,R);
L++;
int k = log2(R - L + 1);
return min(ST[L][k],ST[R - (1<<k) + 1][k]);
}
void getlcp(){
int k = 0;
for(int i = 0;i < n-1;i++){
int j = sa[c[i] - 1];
while(s[i+k] == s[j+k])k++;
lcp[c[i]] = k;
if(k)k--;
}
ST_init();
}
int CompString(int s1,int len1,int s2,int len2){
int tlcp = (s1 == s2?min(len1,len2):LCP(s1,s2));
if(tlcp >= min(len1,len2)){
return len1 < len2?-1:(len1 == len2?0:1);
}
else return s[s1 + tlcp] < s[s2 + tlcp]?-1:(s[s1 + tlcp] == s[s2 + tlcp]?0:1);
}
}sa;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed,ios::floatfield);
cout.precision(12);
int __;
cin >> __;
while(__--){
string s;
cin >> s;
string u = s;
sort(u.begin(),u.end());
int L = -1;
int n = s.size();
for(int i = 0;i < n;i++){
if(s[i] != u[i]){
L = i;
break;
}
}
if(L == -1){
cout << s << endl;
continue;
}
u = s;
reverse(u.begin(),u.end());
s = s + "$" + u;
sa = SA(s);
sa.cal();
sa.getlcp();
int R = L;
for(int i = L;i < n;i++){
if(sa.CompString(L,i - L + 1,2*n - i,i - L + 1) >= 0){
int x = sa.CompString(2*n - R,R - L + 1,2*n - i,R - L + 1);
if(x > 0){
R = i;
}
else if(x == 0 and sa.CompString(R + 1,i - R,2*n - i + R - L + 1,i - R) >= 0){
R = i;
}
}
}
reverse(u.begin(),u.end());
reverse(u.begin() + L,u.begin() + R + 1);
cout << u << endl;
}
return 0;
}
|