Geek asks and answers

Full array of suffixes

A suffix array will index all suffixes for a given list of strings, but what if you try to index all possible unique substrings? I'm a little new to this, so here is an example of what I mean:

Tailored string

abcd

Suffix array indices (at least for my understanding)

(abcd,bcd,cd,d)

I would like to index (all substrings)

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

Is the suffix array what I'm looking for? If so, what should I do to index all the substrings? If not, where should I look? Also, what would I like Google to compare "all substrings" and "suffix substrings"?

+2
source share
3 answers

, , . ,

ABCD BCD CD

, "bc", , , "bc" ( "bcd" ). , , , , .

, LCP ( ) -. . Navarro 2007 (DOI 10.1145/1216370.1216372).

, , . , ,

4 abcd
3 bcd
2 bc
1 d

, , "abcd" 4 "a" , "ab", "abc", "abcd". , , "abcabxdabe",

10 abcabxdabe
1 abe

"a" , "ab" "abe", "a" "ab" .

, ? → , . . "abe", 3 ( ) 2 ( "ab", , ). , , LCP ( ).

:

10 abcabxdabe
11 abe
16 abxdabe
...

. . 13- , , 13. "16 abxdabe" . , ( "xdabe" ), 2- ( 11 13-11 == 2), "abxd" 13- .

+14

, . , , .

, , " ". : , , , . .

+1

You must use the variation "Trie". Essentially, if you have ABCD, create a tree that is a path merge: root-> A-> B-> C-> D, root-> B-> C-> D, root-> C-> D and root → D. Now, on each node, a list of places where the root of the line was found → .-> .-> node is saved.

0
source

More articles:


All Articles