Skip to content

Commit f5dee18

Browse files
author
uwi
committed
'suffix array, lcp arrayを追加'
1 parent d61d8c1 commit f5dee18

2 files changed

Lines changed: 325 additions & 0 deletions

File tree

‎StringAlgorithm/README.md‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
# クラス StringAlgorithm
2+
- - -
3+
4+
文字列アルゴリズム詰め合わせです。
5+
文字列に関する様々なアルゴリズムが入っています。
6+
7+
## suffixArray
8+
9+
```Java
10+
// (1)
11+
public static int[] suffixArray(java.lang.String s)
12+
// (2)
13+
public static int[] suffixArray(char[] s)
14+
// (3)
15+
public static int[] suffixArray(int[] s)
16+
// (4)
17+
public static int[] suffixArray(int[] s, int upper)
18+
```
19+
20+
長さ $n$ の文字列 `s` のSuffix Arrayとして、長さ $n$ のint配列を返す。 Suffix Array `sa`は $(0,1,\ldots ,n-1)$ の順列であって、各 $i=0,1,\cdots , n-2$ について `S[sa[i]..n) < s[sa[i+1]..n)` を満たすもの。
21+
22+
### 制約
23+
24+
- $0\le n\le 10^8$
25+
- (4) $0\le \mathrm{upper}<10^8$
26+
- (4) $s$ のすべての要素 $x$ について $0\le x\le \mathrm{upper}$
27+
28+
### 計算量
29+
30+
- (1) (2) $O(n)$
31+
- (3) 時間 $O(n\log n)$ 空間 $O(n)$
32+
- (4) $O(n+\mathrm{upper})$
33+
34+
## lcpArray
35+
36+
```Java
37+
// (1)
38+
public static int[] lcpArray(java.lang.String s, int[] sa)
39+
// (2)
40+
public static int[] lcpArray(char[] s, int[] sa)
41+
// (3)
42+
public static int[] lcpArray(int[] s, int[] sa)
43+
```
44+
45+
長さ $n$ の文字列 `s` のLCP Arrayとして、長さ $n-1$ の配列を返す。$i$ 番目の要素は `s[sa[i]..n), s[sa[i+1]..n)` の LCP(Longest Common Prefix) の長さ。
46+
47+
### 制約
48+
49+
- `sa` は `s` のSuffix Array
50+
- $1 \le n \le 10^8$
51+
52+
### 計算量
53+
54+
- $O(n)$
55+
56+
## 使用例
57+
[[https://atcoder.jp/contests/practice2/submissions/16585271]]

‎StringAlgorithm/StringAlgorithm.java‎

Lines changed: 268 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,268 @@
1+
import java.util.Arrays;
2+
import java.util.Comparator;
3+
import java.util.function.Consumer;
4+
5+
class StringAlgorithm {
6+
private static int[] saNaive(int[] s) {
7+
int n = s.length;
8+
Integer[] _sa = new Integer[n];
9+
for (int i = 0; i < n; i++) {
10+
_sa[i] = i;
11+
}
12+
Arrays.sort(_sa, (l, r) -> {
13+
while (l < n && r < n) {
14+
if (s[l] != s[r]) return s[l] - s[r];
15+
l++;
16+
r++;
17+
}
18+
return -(l - r);
19+
});
20+
int[] sa = new int[n];
21+
for (int i = 0; i < n; i++) {
22+
sa[i] = _sa[i];
23+
}
24+
return sa;
25+
}
26+
27+
private static int[] saDoubling(int[] s) {
28+
int n = s.length;
29+
Integer[] _sa = new Integer[n];
30+
for (int i = 0; i < n; i++) {
31+
_sa[i] = i;
32+
}
33+
int[] rnk = s;
34+
int[] tmp = new int[n];
35+
36+
for (int k = 1; k < n; k *= 2) {
37+
final int _k = k;
38+
final int[] _rnk = rnk;
39+
Comparator<Integer> cmp = (x, y) -> {
40+
if (_rnk[x] != _rnk[y]) return _rnk[x] - _rnk[y];
41+
int rx = x + _k < n ? _rnk[x + _k] : -1;
42+
int ry = y + _k < n ? _rnk[y + _k] : -1;
43+
return rx - ry;
44+
};
45+
Arrays.sort(_sa, cmp);
46+
tmp[_sa[0]] = 0;
47+
for (int i = 1; i < n; i++) {
48+
tmp[_sa[i]] = tmp[_sa[i - 1]] + (cmp.compare(_sa[i - 1], _sa[i]) < 0 ? 1 : 0);
49+
}
50+
int[] buf = tmp;
51+
tmp = rnk;
52+
rnk = buf;
53+
}
54+
55+
int[] sa = new int[n];
56+
for (int i = 0; i < n; i++) {
57+
sa[i] = _sa[i];
58+
}
59+
return sa;
60+
}
61+
62+
private static final int THRESHOLD_NAIVE = 10;
63+
private static final int THRESHOLD_DOUBLING = 40;
64+
65+
private static int[] sais(int[] s, int upper) {
66+
int n = s.length;
67+
if (n == 0) return new int[0];
68+
if (n == 1) return new int[]{0};
69+
if (n == 2) {
70+
if (s[0] < s[1]) {
71+
return new int[]{0, 1};
72+
} else {
73+
return new int[]{1, 0};
74+
}
75+
}
76+
if (n < THRESHOLD_NAIVE) {
77+
return saNaive(s);
78+
}
79+
if (n < THRESHOLD_DOUBLING) {
80+
return saDoubling(s);
81+
}
82+
83+
int[] sa = new int[n];
84+
boolean[] ls = new boolean[n];
85+
for (int i = n - 2; i >= 0; i--) {
86+
ls[i] = s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1];
87+
}
88+
89+
int[] sumL = new int[upper + 1];
90+
int[] sumS = new int[upper + 1];
91+
92+
for (int i = 0; i < n; i++) {
93+
if (ls[i]) {
94+
sumL[s[i] + 1]++;
95+
} else {
96+
sumS[s[i]]++;
97+
}
98+
}
99+
100+
for (int i = 0; i <= upper; i++) {
101+
sumS[i] += sumL[i];
102+
if (i < upper) sumL[i + 1] += sumS[i];
103+
}
104+
105+
Consumer<int[]> induce = lms -> {
106+
Arrays.fill(sa, -1);
107+
int[] buf = new int[upper + 1];
108+
System.arraycopy(sumS, 0, buf, 0, upper + 1);
109+
for (int d : lms) {
110+
if (d == n) continue;
111+
sa[buf[s[d]]++] = d;
112+
}
113+
System.arraycopy(sumL, 0, buf, 0, upper + 1);
114+
sa[buf[s[n - 1]]++] = n - 1;
115+
for (int i = 0; i < n; i++) {
116+
int v = sa[i];
117+
if (v >= 1 && !ls[v - 1]) {
118+
sa[buf[s[v - 1]]++] = v - 1;
119+
}
120+
}
121+
System.arraycopy(sumL, 0, buf, 0, upper + 1);
122+
for (int i = n - 1; i >= 0; i--) {
123+
int v = sa[i];
124+
if (v >= 1 && ls[v - 1]) {
125+
sa[--buf[s[v - 1] + 1]] = v - 1;
126+
}
127+
}
128+
};
129+
130+
int[] lmsMap = new int[n + 1];
131+
Arrays.fill(lmsMap, -1);
132+
int m = 0;
133+
for (int i = 1; i < n; i++) {
134+
if (!ls[i - 1] && ls[i]) {
135+
lmsMap[i] = m++;
136+
}
137+
}
138+
139+
int[] lms = new int[m];
140+
{
141+
int p = 0;
142+
for (int i = 1; i < n; i++) {
143+
if (!ls[i - 1] && ls[i]) {
144+
lms[p++] = i;
145+
}
146+
}
147+
}
148+
149+
induce.accept(lms);
150+
151+
if (m > 0) {
152+
int[] sortedLms = new int[m];
153+
{
154+
int p = 0;
155+
for (int v : sa) {
156+
if (lmsMap[v] != -1) {
157+
sortedLms[p++] = v;
158+
}
159+
}
160+
}
161+
int[] recS = new int[m];
162+
int recUpper = 0;
163+
recS[lmsMap[sortedLms[0]]] = 0;
164+
for (int i = 1; i < m; i++) {
165+
int l = sortedLms[i - 1], r = sortedLms[i];
166+
int endL = (lmsMap[l] + 1 < m) ? lms[lmsMap[l] + 1] : n;
167+
int endR = (lmsMap[r] + 1 < m) ? lms[lmsMap[r] + 1] : n;
168+
boolean same = true;
169+
if (endL - l != endR - r) {
170+
same = false;
171+
} else {
172+
while (l < endL && s[l] == s[r]) {
173+
l++;
174+
r++;
175+
}
176+
if (l == n || s[l] != s[r]) same = false;
177+
}
178+
if (!same) {
179+
recUpper++;
180+
}
181+
recS[lmsMap[sortedLms[i]]] = recUpper;
182+
}
183+
184+
int[] recSA = sais(recS, recUpper);
185+
186+
for (int i = 0; i < m; i++) {
187+
sortedLms[i] = lms[recSA[i]];
188+
}
189+
induce.accept(sortedLms);
190+
}
191+
return sa;
192+
}
193+
194+
public static int[] suffixArray(int[] s, int upper) {
195+
assert (0 <= upper);
196+
for (int d : s) {
197+
assert (0 <= d && d <= upper);
198+
}
199+
return sais(s, upper);
200+
}
201+
202+
public static int[] suffixArray(int[] s) {
203+
int n = s.length;
204+
Integer[] idx = new Integer[n];
205+
for (int i = 0; i < n; i++) {
206+
idx[i] = i;
207+
}
208+
Arrays.sort(idx, (l, r) -> s[l] - s[r]);
209+
int[] s2 = new int[n];
210+
int now = 0;
211+
for (int i = 0; i < n; i++) {
212+
if (i > 0 && s[idx[i - 1]] != s[idx[i]]) {
213+
now++;
214+
}
215+
s2[idx[i]] = now;
216+
}
217+
return sais(s2, now);
218+
}
219+
220+
public static int[] suffixArray(char[] s) {
221+
int n = s.length;
222+
int[] s2 = new int[n];
223+
for (int i = 0; i < n; i++) {
224+
s2[i] = s[i];
225+
}
226+
return sais(s2, 255);
227+
}
228+
229+
public static int[] suffixArray(java.lang.String s) {
230+
return suffixArray(s.toCharArray());
231+
}
232+
233+
public static int[] lcpArray(int[] s, int[] sa) {
234+
int n = s.length;
235+
assert (n >= 1);
236+
int[] rnk = new int[n];
237+
for (int i = 0; i < n; i++) {
238+
rnk[sa[i]] = i;
239+
}
240+
int[] lcp = new int[n - 1];
241+
int h = 0;
242+
for (int i = 0; i < n; i++) {
243+
if (h > 0) h--;
244+
if (rnk[i] == 0) {
245+
continue;
246+
}
247+
int j = sa[rnk[i] - 1];
248+
for (; j + h < n && i + h < n; h++) {
249+
if (s[j + h] != s[i + h]) break;
250+
}
251+
lcp[rnk[i] - 1] = h;
252+
}
253+
return lcp;
254+
}
255+
256+
public static int[] lcpArray(char[] s, int[] sa) {
257+
int n = s.length;
258+
int[] s2 = new int[n];
259+
for (int i = 0; i < n; i++) {
260+
s2[i] = s[i];
261+
}
262+
return lcpArray(s2, sa);
263+
}
264+
265+
public static int[] lcpArray(java.lang.String s, int[] sa) {
266+
return lcpArray(s.toCharArray(), sa);
267+
}
268+
}

0 commit comments

Comments
 (0)