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 1 commit
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
Prev Previous commit
Next Next commit
'int[]版suffix arrayの座標圧縮を高速化'
  • Loading branch information
uwi
uwi committed Sep 20, 2020
commit 8379f2186c93ebf0b5bd605fe9fddecf6f1e9b9f
26 changes: 13 additions & 13 deletions StringAlgorithm/StringAlgorithm.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,4 +1,4 @@
import java.util.stream.IntStream;
import java.util.Arrays;

class StringAlgorithm {
private static int[] saNaive(int[] s) {
Expand Down Expand Up @@ -228,22 +228,22 @@ public static int[] suffixArray(int[] s, int upper) {
return sais(s, upper);
}

public static int[] suffixArray(int[] s) {
public static int[] suffixArray(int[] s)
{
int n = s.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) {
idx[i] = i;
int[] vals = Arrays.copyOf(s, n);
java.util.Arrays.sort(vals);
int p = 1;
for(int i = 1;i < n;i++){
if(vals[i] != vals[i-1]){
vals[p++] = vals[i];
}
}
java.util.Arrays.sort(idx, (l, r) -> s[l] - s[r]);
int[] s2 = new int[n];
int now = 0;
for (int i = 0; i < n; i++) {
if (i > 0 && s[idx[i - 1]] != s[idx[i]]) {
now++;
}
s2[idx[i]] = now;
for(int i = 0;i < n;i++){
s2[i] = java.util.Arrays.binarySearch(vals, 0, p, s[i]);
}
return sais(s2, now);
return sais(s2, p);
}

public static int[] suffixArray(char[] s) {
Expand Down