-
Notifications
You must be signed in to change notification settings - Fork 0
/
stringsheet.bbl
126 lines (102 loc) · 4.25 KB
/
stringsheet.bbl
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
\begin{thebibliography}{10}
\bibitem{benoit05dfuds}
D.~Benoit, E.~D. Demaine, J.~I. Munro, R.~Raman, V.~Raman, and S.~S. Rao.
\newblock Representing trees of higher degree.
\newblock {\em Algorithmica}, 43(4):275--292, 2005.
\bibitem{burrows94bwt}
M.~Burrows and D.~J. Wheeler.
\newblock A block sorting lossless data compression algorithm.
\newblock Technical Report 124, Digital Equipment Corporation, Palo Alto,
California, 1994.
\bibitem{chen58lyndon}
K.~T. Chen, R.~H. Fox, and R.~C. Lyndon.
\newblock Free differential calculus, {IV}. {T}he quotient groups of the lower
central series.
\newblock {\em Annals of Mathematics}, pages 81--95, 1958.
\bibitem{crochemore08lpf}
M.~Crochemore and L.~Ilie.
\newblock Computing longest previous factor in linear time and applications.
\newblock {\em Inf. Process. Lett.}, 106(2):75--80, 2008.
\bibitem{fan06periodicity}
K.~Fan, S.~J. Puglisi, W.~F. Smyth, and A.~Turpin.
\newblock A new periodicity lemma.
\newblock {\em {SIAM} J. Discrete Math.}, 20(3):656--668, 2006.
\bibitem{ferragina00fmindex}
P.~Ferragina and G.~Manzini.
\newblock Opportunistic data structures with applications.
\newblock In {\em Proc.\ FOCS}, pages 390--398, 2000.
\bibitem{ferragina05index}
P.~Ferragina and G.~Manzini.
\newblock Indexing compressed text.
\newblock {\em J. {ACM}}, 52(4):552--581, 2005.
\bibitem{fine65uniqueness}
N.~J. Fine and H.~S. Wilf.
\newblock Uniqueness theorems for periodic functions.
\newblock {\em Proceedings of the American Mathematical Society},
16(1):109--114, 1965.
\bibitem{franek03lpf}
F.~Franek, J.~Holub, W.~F. Smyth, and X.~Xiao.
\newblock Computing quasi suffix arrays.
\newblock {\em Journal of Automata, Languages and Combinatorics},
8(4):593--606, 2003.
\bibitem{fredman93fusion}
M.~L. Fredman and D.~E. Willard.
\newblock Surpassing the information theoretic bound with fusion trees.
\newblock {\em J. Comput. Syst. Sci.}, 47(3):424--436, 1993.
\bibitem{grossi05csa}
R.~Grossi and J.~S. Vitter.
\newblock Compressed suffix arrays and suffix trees with applications to text
indexing and string matching.
\newblock {\em {SIAM} J. Comput.}, 35(2):378--407, 2005.
\bibitem{hagerup98sorting}
T.~Hagerup.
\newblock Sorting and searching on the word {RAM}.
\newblock In {\em Proc.\ STACS}, volume 1373 of {\em LNCS}, pages 366--398,
1998.
\bibitem{jacobson89rank}
G.~Jacobson.
\newblock Space-efficient static trees and graphs.
\newblock In {\em Proc.\ FOCS}, pages 549--554, 1989.
\bibitem{karkkainen09plcp}
J.~K{\"{a}}rkk{\"{a}}inen, G.~Manzini, and S.~J. Puglisi.
\newblock Permuted longest-common-prefix array.
\newblock In {\em Proc.\ CPM}, volume 5577 of {\em LNCS}, pages 181--192, 2009.
\bibitem{kasai01lcp}
T.~Kasai, G.~Lee, H.~Arimura, S.~Arikawa, and K.~Park.
\newblock Linear-time longest-common-prefix computation in suffix arrays and
its applications.
\newblock In {\em Proc.\ CPM}, volume 2089 of {\em LNCS}, pages 181--192, 2001.
\bibitem{lee09rank}
S.~Lee and K.~Park.
\newblock Dynamic rank/select structures with applications to run-length
encoded texts.
\newblock {\em Theor. Comput. Sci.}, 410(43):4402--4413, 2009.
\bibitem{manber93sa}
U.~Manber and E.~W. Myers.
\newblock Suffix arrays: {A} new method for on-line string searches.
\newblock {\em {SIAM} J. Comput.}, 22(5):935--948, 1993.
\bibitem{raskhodnikova13sublinear}
S.~Raskhodnikova, D.~Ron, R.~Rubinfeld, and A.~D. Smith.
\newblock Sublinear algorithms for approximating string compressibility.
\newblock {\em Algorithmica}, 65(3):685--709, 2013.
\bibitem{siren10plcp}
J.~Sir{\'{e}}n.
\newblock Sampled longest common prefix array.
\newblock In {\em Proc.\ CPM}, volume 6129 of {\em LNCS}, pages 227--237, 2010.
\bibitem{storer82lzss}
J.~A. Storer and T.~G. Szymanski.
\newblock Data compression via textural substitution.
\newblock {\em J. {ACM}}, 29(4):928--951, 1982.
\bibitem{yao81sorted}
A.~C. Yao.
\newblock Should tables be sorted?
\newblock {\em J. {ACM}}, 28(3):615--628, 1981.
\bibitem{ziv77lz}
J.~Ziv and A.~Lempel.
\newblock A universal algorithm for sequential data compression.
\newblock {\em {IEEE} Trans. Information Theory}, 23(3):337--343, 1977.
\bibitem{ziv78lz}
J.~Ziv and A.~Lempel.
\newblock Compression of individual sequences via variable-rate coding.
\newblock {\em {IEEE} Trans. Information Theory}, 24(5):530--536, 1978.
\end{thebibliography}