Skip to content

#4 Suffix Arrayの高速化 #38

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
NASU41 merged 7 commits into from
Sep 21, 2020
Merged

#4 Suffix Arrayの高速化 #38

Changes from 3 commits
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
10a92d1
untracked files on improve-sa: c13664f MathLibrary
Sep 20, 2020
ca94592
index on improve-sa: c13664f MathLibrary
Sep 20, 2020
34bf618
WIP on improve-sa: c13664f MathLibrary
Sep 20, 2020
03f55f4
Merge branch 'master' into StringAlgorithm
Sep 20, 2020
0123f59
'saNaiveとsaDoublingを高速化。しきい値調整。'
Sep 20, 2020
8379f21
'int[]版suffix arrayの座標圧縮を高速化'
Sep 20, 2020
a61a88d
'不要なファイルを削除'
Sep 20, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
48 changes: 28 additions & 20 deletions StringAlgorithm/StringAlgorithm.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,58 +1,66 @@
import java.util.stream.IntStream;

class StringAlgorithm {
private static int[] saNaive(int[] s) {
int n = s.length;
Integer[] _sa = new Integer[n];
for (int i = 0; i < n; i++) {
_sa[i] = i;
int[] sa = new int[n];
for(int i = 0;i < n;i++){
sa[i] = i;
}
java.util.Arrays.sort(_sa, (l, r) -> {
insertionsortUsingComparator(sa, (l, r) -> {
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] - s[r];
l++;
r++;
}
return -(l - r);
});
int[] sa = new int[n];
for (int i = 0; i < n; i++) {
sa[i] = _sa[i];
}
return sa;
}

private static int[] saDoubling(int[] s) {
public static int[] saDoubling(int[] s) {
int n = s.length;
Integer[] _sa = new Integer[n];
for (int i = 0; i < n; i++) {
_sa[i] = i;
int[] sa = new int[n];
for(int i = 0;i < n;i++){
sa[i] = i;
}
int[] rnk = s;
int[] tmp = new int[n];

for (int k = 1; k < n; k *= 2) {
final int _k = k;
final int[] _rnk = rnk;
java.util.Comparator<Integer> cmp = (x, y) -> {
java.util.function.IntBinaryOperator cmp = (x, y) -> {
if (_rnk[x] != _rnk[y]) return _rnk[x] - _rnk[y];
int rx = x + _k < n ? _rnk[x + _k] : -1;
int ry = y + _k < n ? _rnk[y + _k] : -1;
return rx - ry;
};
java.util.Arrays.sort(_sa, cmp);
tmp[_sa[0]] = 0;
insertionsortUsingComparator(sa, cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[_sa[i]] = tmp[_sa[i - 1]] + (cmp.compare(_sa[i - 1], _sa[i]) < 0 ? 1 : 0);
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.applyAsInt(sa[i - 1], sa[i]) < 0 ? 1 : 0);
}
int[] buf = tmp;
tmp = rnk;
rnk = buf;
}
return sa;
}

int[] sa = new int[n];
for (int i = 0; i < n; i++) {
sa[i] = _sa[i];
private static void insertionsortUsingComparator(int[] a, java.util.function.IntBinaryOperator comparator) {
final int n = a.length;
for (int i = 1; i < n; i++) {
final int tmp = a[i];
if (comparator.applyAsInt(a[i - 1], tmp) > 0) {
int j = i;
do {
a[j] = a[j - 1];
j--;
} while (j > 0 && comparator.applyAsInt(a[j - 1], tmp) > 0);
a[j] = tmp;
}
}
return sa;
}

private static final int THRESHOLD_NAIVE = 10;
Expand Down