字符串算法非常常见，并且在一般的算法竞赛中，往往都是以压轴题的形式出现
这里先研究字符串和它的子串的一些关系
常用的字符串和它的子串的处理工具
主要有后缀数组和后缀自动机
后缀数组初步算法
思想概述
后缀数组的思想理解起来并不复杂
具体的见下图：
其中精妙的地方在于：
比如后缀{a,abra,abracadabra}
都存在a这个前缀，这个时候用基数排序，把频次转换成索引
然后跟高考成绩排名一样，依次对字符串排序下来
然后接着处理第二个字符
具体的程序实现如下
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
| //
// main.cpp
// suffixArray
//
// Created by zhangmin chen on 2019/2/14.
// Copyright © 2019 zhangmin chen. All rights reserved.
using namespace std;
/* string sort test:
int main() {
freopen("input.txt", "r", stdin);
string tmp;
vector<string> ans;
while(getline(cin, tmp)) {
ans.push_back(tmp);
}
sort(ans.begin(), ans.end());
for(auto& i : ans)
cout << i << endl;
}
*/
class suffixArray {
private:
string* str;
int N;
int lcp(string s, string t) {
int len = (int) min(s.length(), t.length());
for(int i = 0; i < len; i++) if(s[i] != t[i])
return i;
return len;
}
public:
suffixArray(string text) {
//
N = (int)text.length();
str = new string[N+1];
for(int i = 0; i < N; i++)
str[i] = text.substr(i);
sort(str, str+N);
}
~suffixArray() { delete[] str; }
int length() { return N; }
string select(int i) { return str[i]; }
int index(int i) { return (int) (N - str[i].length()); }
int lcp(int i) { return lcp(str[i], str[i-1]); }
int rank(string key) {
int lo = 0, hi = N-1;
while(lo <= hi) {
int mid = lo + (hi-lo)/2;
int cmp = strcmp(key.c_str(), str[mid].c_str());
if(cmp < 0) hi = mid-1;
else if(cmp > 0) lo = mid+1;
else return mid;
}
return lo;
}
};
int main() {
freopen("input.txt", "r", stdin);
string tmp;
cin >> tmp;
suffixArray sa(tmp);
printf(" i ind lcp rnk select\n");
printf("---------------------------\n");
for(int i = 0; i < tmp.length(); i++) {
int idx = sa.index(i);
string ith = "\"" + tmp.substr(idx) + "\"";
assert(tmp.substr(idx) == sa.select(i));
// most important!
int rk = sa.rank(tmp.substr(idx));
if(i == 0)
printf("%3d %3d %3s %3d %s\n", i, idx, "-", rk, ith.c_str());
else {
int lcp = sa.lcp(i);
printf("%3d %3d %3d %3d %s\n", i, idx, lcp, rk, ith.c_str());
}
}
}
|
后缀数组Manber-Myers算法
思想概述
上述朴素算法，效率是比较低的
我们每一次都对字符串从头到尾扫描一遍
最坏情况下，算法的效率是O(n2/2)
如何改进呢？
能不能在基数排序str[0]完成之后，利用str[0]的信息，来接着处理str[1], str[2]…呢
先这样想，我们把第一位的结果，当成是第二位的可以不可以呢？
字符串右移一位，会是什么情况呢？
具体的算法图解如下：
其实就相当于把串整体下移一位
利用第一次的结果排序第二次
这样前缀的值就可以确定下来，我们可以尝试求解LCP
LCP求解
最后的结果是：
UVA11107
来看一道题目
Life Forms
分析：
实现：
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
149
150
151
152
153
154
155
156
157
158
159
160
| //
// main.cpp
// uva11107
//
// Created by zhangmin chen on 2019/2/16.
// Copyright © 2019 zhangmin chen. All rights reserved.
//
using namespace std;
const int maxn = 1001 * 100 + 10;
struct suffixArray {
int str[maxn], sa[maxn], rank[maxn], lcp[maxn];
int c[maxn], t1[maxn], t2[maxn];
int n;
void init() { n = 0; memset(sa, 0, sizeof(sa)); }
void buildSa(int Rdx) {
int i, *x = t1, *y = t2;
for(i = 0; i < Rdx; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[i] = str[i]]++;
for(i = 1; i < Rdx; i++) c[i] += c[i-1];
for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
for(int offset = 1; offset <= n; offset <<= 1) {
int p = 0;
for(i = n-offset; i < n; i++) y[p++] = i;
for(i = 0; i < n; i++) if(sa[i] >= offset) y[p++] = sa[i] - offset;
// radix sort
for(i = 0; i < Rdx; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 1; i < Rdx; i++) c[i] += c[i-1];
for(i = n-1; i >= 0; i--) { sa[--c[x[y[i]]]] = y[i]; y[i] = 0; }
// rebuild x and y
swap(x, y); x[sa[0]] = 0; p = 1;
for(i = 1; i < n; i++)
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+offset] == y[sa[i]+offset] ? p-1 : p++;
if(p >= n) break;
Rdx = p;
}
}
void getLcp() {
int k = 0;
for(int i = 0; i < n; i++) rank[sa[i]] = i;
for(int i = 0; i < n; i++) {
if(rank[i] == 0) continue;
if(k) k--;
int j = sa[rank[i] - 1];
while(str[i+k] == str[j+k]) k++;
lcp[rank[i]] = k;
}
}
};
const int maxl = 1000 + 10;
const int maxc = 100 + 10;
suffixArray sa;
int n;
char word[maxl];
int flag[maxc];
int idx[maxn];
void add(int ch, int wid) {
// add alpha in sa
idx[sa.n] = wid;
sa.str[sa.n++] = ch;
}
bool judge(int left, int right) {
memset(flag, 0, sizeof(flag));
if(right-left <= n/2) return false;
int cnt = 0;
for(int i = left; i < right; i++) {
int wid = idx[sa.sa[i]];
if(wid != n && flag[wid] == 0) { flag[wid] = 1; cnt++; }
}
return cnt > n/2;
}
void printSub(int l, int r) {
for(int i = l; i < r; i++) {
printf("%c", sa.str[i]-1+'a');
}
printf("\n");
}
bool okForLength(int len, bool print) {
// binary search
int left = 0;
for(int right = 1; right <= sa.n; right++) if(right == sa.n || sa.lcp[right] < len) {
// a new block
if(judge(left, right)) {
if(print) printSub(sa.sa[left], sa.sa[left]+len);
// is sa.sa[left], printout original str[]
else return true;
}
left = right;
}
return false;
}
void solve(int maxlen) {
//
if(!okForLength(1, false)) printf("?\n");
else {
int l = 1, r = maxlen, mid;
while(l < r) {
mid = l + (r-l+1)/2;
if(okForLength(mid, false)) l = mid;
else r = mid-1;
}
okForLength(l, true);
}
}
int main() {
freopen("input.txt", "r", stdin);
int kase = 0;
while(scanf("%d", &n) == 1 && n) {
if(kase++ > 0) printf("\n");
int maxlen = 0;
sa.init();
for(int i = 0; i < n; i++) {
scanf("%s", word);
int sz = (int)strlen(word);
maxlen = max(maxlen, sz);
for(int j = 0; j < sz; j++)
add(word[j]-'a'+1, i);
add(100+i, n);
}
add(0, n);
if(n == 1) printf("%s\n", word);
else {
sa.buildSa(100+n);
sa.getLcp();
solve(maxlen);
}
}
return 0;
}
|
这道题目的后缀数组模版比较常用
后缀自动机理论
后缀自动机则是比后缀数组更为强大的工具
它能够在线性时间内求出子串
后缀自动机的构造方式
endpos()函数
后缀链接
实现中重复添加字符的处理方法
hihocoder1445
具体的题目见
后缀自动机二·重复旋律5
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
| //
// main.cpp
// hiho1445
//
// Created by zhangmin chen on 2019/2/22.
// Copyright © 2019 zhangmin chen. All rights reserved.
//
typedef long long llong;
using namespace std;
const int maxl = 1000000 + 10;
const int maxn = 2 * maxl;
struct SAM {
int maxlen[maxn], trans[maxn][26], link[maxn], size, last;
SAM() {
Set(maxlen, 0); Set(trans, 0); Set(link, 0);
size = last = 1;
}
void extend(int ch) {
//
int cur = ++size, p = last;
maxlen[cur] = maxlen[p] + 1;
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
// then, we try to change the link of cur, link[cur] = ?
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++size;
maxlen[clone] = maxlen[p] + 1;
Cpy(trans[clone], trans[q]); link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[q] = link[cur] = clone;
}
}
last = cur;
}
};
SAM sam;
char str[maxl];
int main() {
freopen("input.txt", "r", stdin);
scanf("%s", str);
for(int i = 0; str[i]; i++) sam.extend(str[i] - 'a');
llong ans = 0;
for(int i = 1; i <= sam.size; i++) {
if(i == 1) continue;
ans += sam.maxlen[i] - sam.maxlen[sam.link[i]];
}
cout << ans;
}
|
求任意的长度为k的子串出现的次数
hihocoder1449
后缀自动机三·重复旋律6
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
| //
// main.cpp
// hiho1449
//
// Created by zhangmin chen on 2019/2/22.
// Copyright © 2019 zhangmin chen. All rights reserved.
//
typedef long long llong;
using namespace std;
const int maxl = 1000000 + 10;
const int maxn = 2 * maxl;
llong cnt[maxn];
struct SAM {
int maxlen[maxn], trans[maxn][26], link[maxn], size, last;
SAM() {
Set(maxlen, 0); Set(trans, 0); Set(link, 0);
size = last = 1;
}
void extend(int ch) {
//
int cur = ++size, p = last;
maxlen[cur] = maxlen[p] + 1;
cnt[cur] = 1;
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++size;
maxlen[clone] = maxlen[p] + 1;
Cpy(trans[clone], trans[q]); link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
};
SAM sam;
char str[maxl];
vector<int> G[maxn];
int indeg[maxn];
llong ans[maxn];
void build() {
REP(i, 1, sam.size) { G[i].push_back(sam.link[i]); indeg[sam.link[i]]++; }
}
void topo() {
queue<int> que;
build();
REP(i, 0, sam.size) if(!indeg[i]) que.push(i);
while(!que.empty()) {
int u = que.front(); que.pop();
for(int v : G[u]) {
// ans[sam.maxlen[u]] = max(ans[sam.maxlen[u]], cnt[u]);
cnt[v] += cnt[u];
if(!(--indeg[v])) que.push(v);
}
}
REP(i, 1, sam.size) ans[sam.maxlen[i]] = max(ans[sam.maxlen[i]], cnt[i]);
// FOR(i, 1, sam.size) debug(cnt[i]);
}
int main() {
//
freopen("input.txt", "r", stdin);
string str;
cin >> str;
for(int i = 0; i < str.length(); i++) sam.extend(str[i] - 'a');
topo();
for(int i = (int)str.length(); i >= 1; i--) ans[i] = max(ans[i], ans[i+1]);
for(int i = 1; i <= str.length(); i++) cout << ans[i] << endl;
}
|
连接不同的子串，标识符分隔，再拓扑排序
这样可以把所有不同的串整合到一起
hihocoder1457
后缀自动机四·重复旋律7
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
|
//
// main.cpp
// hiho1457
//
// Created by zhangmin chen on 2019/2/23.
// Copyright © 2019 zhangmin chen. All rights reserved.
//
typedef long long llong;
using namespace std;
const int maxl = 1000000 + 10;
const int maxn = 2 * maxl;
const llong MOD = 1000000007;
struct SAM {
int maxlen[maxn], trans[maxn][26], link[maxn], size, last;
SAM() {
Set(maxlen, 0); Set(trans, 0); Set(link, 0);
size = last = 1;
}
void extend(int ch) {
int cur = ++size, p = last;
maxlen[cur] = maxlen[p] + 1;
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++size;
maxlen[clone] = maxlen[p] + 1;
Cpy(trans[clone], trans[q]); link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
};
SAM sam;
const int spc = 10;
int indeg[maxn];
llong cnt[maxn], val[maxn];
int main() {
freopen("input.txt", "r", stdin);
// llong ans = 0;
Set(cnt, 0); Set(val, 0); Set(indeg, 0);
int n;
scanf("%d", &n);
string str;
while(n--) {
cin >> str;
for(int i = 0; i < str.length(); i++) sam.extend(str[i]-'0');
if(n != 0) sam.extend(10);
}
queue<int> que; que.push(1); cnt[1] = 1;
REP(i, 1, sam.size) REP(j, 0, spc) ++indeg[sam.trans[i][j]];
while(!que.empty()) {
int u = que.front(); que.pop();
REP(i, 0, spc) {
int v = sam.trans[u][i]; if(!v) continue;
if(i != 10) {
(cnt[v] += cnt[u]) %= MOD;
(val[v] += val[u] * 10 % MOD + (llong)(i * cnt[u] % MOD)) %= MOD;
}
if(!(--indeg[v])) que.push(v);
}
}
llong ans = 0;
for(int i = 1; i <= sam.size; i++) ans = (ans + val[i]) % MOD;
printf("%lld\n", ans);
}
|
串T在串S中的出现次数
这个简单，如果是循环同构串，就比较复杂了
hihocoder1465
后缀自动机五·重复旋律8
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
| //
// main.cpp
// hiho1465-2
//
// Created by zhangmin chen on 2019/2/25.
// Copyright © 2019 zhangmin chen. All rights reserved.
//
using namespace std;
typedef long long llong;
const int maxl = 1000000 + 10;
const int maxn = 2 * maxl;
struct SAM {
int maxlen[maxn], trans[maxn][26], link[maxn], size, last;
int tag[maxn], indeg[maxn], endpos[maxn];
SAM() {
Set(maxlen, 0); Set(trans, 0); Set(link, 0); Set(tag, 0);
Set(indeg, 0); Set(endpos, 0);
size = last = 1;
}
void extend(int ch) {
int cur = ++size, p = last;
tag[cur] = 1;
maxlen[cur] = maxlen[p] + 1;
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
// relink cur
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++size; tag[clone] = 0;
maxlen[clone] = maxlen[p] + 1;
Cpy(trans[clone], trans[q]); link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
void build() {
for(int i = 1; i <= size; i++) ++indeg[link[i]];
queue<int> que;
for(int i = 1; i <= size; i++) if(indeg[i] == 0) {
que.push(i); endpos[i] = 1;
}
while(!que.empty()) {
int x = que.front(); que.pop();
if(x == 0) continue;
int y = link[x]; indeg[y]--;
endpos[y] += endpos[x];
if(indeg[y] == 0) {
if(tag[y]) endpos[y]++;
que.push(y);
}
}
}
};
SAM sam;
int version[maxn];
llong solve(string& str, int num) {
int len = (int)str.length(); int base = len;
string str2 = str.substr(0, len-1);
str += str2;
len = 2*len - 1;
int u = 1, lcs = 0;
llong ans = 0;
for(int i = 0; i < len; i++) {
int ch = str[i] - 'a';
if(sam.trans[u][ch]) { u = sam.trans[u][ch]; lcs++; }
else {
for(; u && !sam.trans[u][ch]; u = sam.link[u]);
if(!u) { u = 1; lcs = 0; }
else {
lcs = sam.maxlen[u] + 1;
u = sam.trans[u][ch];
}
}
if(lcs > base) {
while(sam.maxlen[sam.link[u]] >= base) { u = sam.link[u]; lcs = sam.maxlen[u]; }
}
if(lcs >= base && version[u] != num) {
version[u] = num;
ans += sam.endpos[u];
}
}
return ans;
}
string str;
int main() {
freopen("input.txt", "r", stdin);
cin >> str;
for(int i = 0; i < str.length(); i++) sam.extend(str[i] - 'a');
sam.build();
int kase;
scanf("%d", &kase);
for(int k = 1; k <= kase; k++) {
cin >> str;
llong res = solve(str, k);
printf("%lld\n", res);
}
}
|
后缀自动机+SG函数
这个题目难度比较大，和博弈论综合
hihocoder1466
后缀自动机六·重复旋律9
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
| //
// main.cpp
// hiho1466
//
// Created by zhangmin chen on 2019/2/28.
// Copyright © 2019 zhangmin chen. All rights reserved.
//
using namespace std;
typedef long long llong;
const int maxl = 100000 + 10;
const int maxn = 2*maxl;
const int N = 27;
// cnt(pre, SG())
struct SAM {
int len[maxn], trans[maxn][26], link[maxn], size, last;
// other arr[]
int sg[maxn];
llong cnt[maxn][N+1];
SAM() {
Set(len, 0); Set(trans, 0); Set(link, 0);
Set(sg, -1);
size = 1;
last = 1;
}
void extend(int ch) {
int cur = ++size, p = last;
// 1 is the " "
len[cur] = len[p] + 1;
//debug(cur);
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
// relink cur
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(len[p] + 1 == len[q]) link[cur] = q;
else {
int clone = ++size;
len[clone] = len[p] + 1;
Cpy(trans[clone], trans[q]); link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
int SG(int x) {
if(sg[x] != -1) return sg[x];
bool flag[28];
for(int i = 0; i < 27; i++) flag[i] = 0;
for(int i = 0; i < 26; i++) {
int to = trans[x][i];
//debug(to);
if(to == 0) continue;
flag[SG(to)] = 1;
for(int j = 0; j < 27; j++) cnt[x][j] += cnt[to][j];
// I made a bug here, is j
}
for(int i = 0; i < 27; i++) if(!flag[i]) {
sg[x] = i; break;
}
cnt[x][sg[x]]++;
for(int i = 0; i < 27; i++) cnt[x][27] += cnt[x][i];
return sg[x];
}
void Debug() {
for(int i = 0; i <= size; i++) {
printf("i: %d:\n", i);
for(int j = 0; j < 28; j++) /*printf("%lld ", cnt[i][j]);*/ debug(cnt[i][j]);
printf("sg:: %d\n", sg[i]);
/*
for(int j = 0; j < 26; j++)
debug(trans[i][j]);
*/
}
}
};
SAM A, B;
char res[2][maxn];
llong k;
// cntA[u][sg()] cntB[v][sg()]
// (sa_u, sb_v)
llong cost(int u, int v) {
llong ans = 0;
for(int i = 0; i < 27; i++)
ans += 1LL * A.cnt[u][i] * (B.cnt[v][27] - B.cnt[v][i]);
return ans;
}
// p is the item of resA[p]
// A.sg[x] x = {_, a, b, ab}
int dfsA(int p, int x) {
llong ct = B.cnt[1][27] - B.cnt[1][A.sg[x]];
//debug(ct);
//debug(k);
//cout << endl;
// B from 0 to match
if(k <= ct) return x;
else {
k -= ct;
for(int i = 0; i < 26; i++) {
int to = A.trans[x][i];
if(to == 0) continue;
//debug(to);
llong ct2 = cost(to, 1);
if(ct2 < k) k -= ct2;
else {
res[0][p] = 'a' + i;
return dfsA(p+1, to);
// return dfsA(next)
}
}
return -1;
}
/*
// follow the path in SAM
for(int i = 0; i < 26; i++) {
int to = A.trans[x][i];
if(to == 0) continue;
llong ct2 = cost(to, 1);
if(ct2 < k) k -= ct2;
else {
// ct2 >= k, we follow the path and extend char
// to reduce ct2
res[0][p] = 'a' + i;
debug(res[0]);
dfsA(p+1, to);
}
}
if(k > ct) return -1;
else return x;
*/
}
void dfsB(int p, int x, int T) {
k -= A.sg[T] != B.sg[x];
if(k == 0) return;
for(int i = 0; i < 26; i++) {
int to = B.trans[x][i];
if(to == 0) continue;
llong ct = B.cnt[to][27] - B.cnt[to][A.sg[T]];
if(ct < k) k -= ct;
else {
// reduce ct
res[1][p] = 'a' + i;
dfsB(p+1, to, T);
return;
}
}
}
int main() {
freopen("input.txt", "r", stdin);
string a, b;
cin >> k;
cin >> a >> b;
//debug(a[0]);
for(int i = 0; i < a.length(); i++) A.extend(a[i] - 'a');
A.SG(1);
//A.Debug();
for(int i = 0; i < b.length(); i++) B.extend(b[i] - 'a');
B.SG(1);
//B.Debug();
int T = dfsA(0, 1);
//debug(T);
if(T == -1) {
printf("NO\n");
return 0;
}
dfsB(0, 1, T);
puts(res[0]);
puts(res[1]);
}
|
微信
支付宝
