Максим Крошемор , Тьерри Лекрок , Войцех Риттер - Алгоритмы обработки текста: 125 задач с решениями

Prezza. String attractors. CoRR, abs/1709.05314, 2017.
[203] S. J. Puglisi, J. Simpson and W. F. Smyth. How many runs can a string contain?
Theor. Comput. Sci., 401(1–3):165–171, 2008.
[204] J. Radoszewski and W. Rytter. On the structure of compacted subword graphs
of Thue-Morse words and their applications. J. Discrete Algorithms, 11:15–24,
2012.
[205] N. Rampersad, J. Shallit and M. Wang. Avoiding large squares in infinite binary
words. Theor. Comput. Sci., 339(1):19–34, 2005.
[206] D. Repke and W. Rytter. On semi-perfect de Bruijn words. Theor. Comput. Sci.,
720:55–63, 2018.
[207] A. Restivo and S. Salemi. Overlap-free words on two symbols. In M. Nivat and
D. Perrin, eds., Automata on Infinite Words, Ecole de Printemps d’In­formatique
Théorique, Le Mont Dore, 14–18 May, 1984, vol. 192, Lecture Notes in Computer
Science, pp. 198–206. Springer, 1985.
[208] C. Reutenauer. From Christoffel Words to Markov Numbers. Oxford University
Press, 2018.
[209] G. Rozenberg and A. Salomaa. The Mathematical Theory of L Systems. Academic
Press, 1980.
[210] M. Rubinchik and A. M. Shur. Eertree: An efficient data structure for processing
palindromes in strings. CoRR, abs/1506.04862, 2015.
[211] F. Ruskey and A. Williams. An explicit universal cycle for the (n – 1)-permutations of an n-set. ACM Trans. Algorithms, 6(3):45:1–45:12, 2010.
[212] W. Rytter. A correct preprocessing algorithm for Boyer-Moore string-searching.
SIAM J. Comput., 9(3):509–512, 1980.
[213] W. Rytter. The structure of subword graphs and suffix trees of Fibonacci words.
Theor. Comput. Sci., 363(2):211–223, 2006.
[214] W. Rytter. The number of runs in a string. Informat. Comput., 205(9):1459–1469,
2007.
[215] W. Rytter. Two fast constructions of compact representations of binary words
with given set of periods. Theor. Comput. Sci., 656:180–187, 2016.
[216] W. Rytter. Computing the k-th letter of Fibonacci word. Personal communication, 2017.
[217] A. A. Sardinas and G. W. Patterson. A necessary and sufficient condition for the
unique decomposition of coded messages. Research Division Report 50–27, Moore
School of Electrical Engineering, University of Pennsylvania, 1950.
[218] J. Sawada and P. Hartman. Finding the largest fixed-density necklace and Lyndon word. Inf. Process. Lett., 125:15–19, 2017.

Литература  307

[219] J. Sawada, A. Williams and D. Wong. A surprisingly simple de Bruijn sequence
construction. Discrete Math., 339(1):127–131, 2016.
[220] B. Schieber. Computing a minimum weight-link path in graphs with the concave
Monge property. J. Algorithms, 29(2):204–222, 1998.
[221] M. Sciortino and L. Q. Zamboni. Suffix automata and standard sturmian words.
In T. Harju, J. Karhumäki and A. Lepistö, eds., Developments in Language Theory,
11th International Conference, DLT 2007, Turku, Finland, 3–6 July, 2007, Proceedings, vol. 4588, Lecture Notes in Computer Science, pp. 382–398. Springer, 2007.
[222] J. Shallit. On the maximum number of distinct factors of a binary string. Graphs
Combinat., 9(2–4):197–200, 1993.
[223] Y. Shiloach. A fast equivalence-checking algorithm for circular lists. Inf. Process.
Lett., 8(5):236–238, 1979.
[224] R. M. Silva, D. Pratas, L. Castro, A. J. Pinho and P. J. S. G. Ferreira. Three minimal
sequences found in ebola virus genomes and absent from human DNA. Bioinformatics, 31(15):2421–2425, 2015.
[225] I. Simon. String matching algorithms and automata. In R. Baeza-Yates and
N. Ziviani, eds., Proceedings of the 1st South American Workshop on String Processing, pp. 151–157, Belo Horizonte, Brasil, 1993. Universidade Federal de
Minas Gerais.
[226] S. S. Skiena. The Algorithm Design Manual. 2nd ed., Springer, 2008.
[227] T. Skolem. On certain distributions of integers in pairs with given differences.
Math. Scand., 5:57–68, 1957.
[228] B. Smyth. Computing Patterns in Strings. Pearson Education Limited, 2003.
[229] M. Szykula. Improving the upper bound on the length of the shortest reset word.
In R. Niedermeier and B. Vallée, eds., 35th Symposium on Theoretical Aspects
of Computer Science, STACS 2018, 28 February – 3 March 2018, Caen, France,
vol. 96, LIPIcs, pp. 56:1–56:13. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2018.
[230] J. Tarhio and E. Ukkonen. A greedy approximation algorithm for constructing
shortest common superstrings. Theor. Comput. Sci., 57:131–145, 1988.
[231] Z. Tronícek and B. Melichar. Directed acyclic subsequence graph. In J. Holub
and M. Simánek, eds., Proceedings of the Prague Stringology Club Workshop 1998,
Prague, Czech Republic, 3–4 September, 1998, pp. 107–118. Department of
Computer Science and Engineering, Faculty of Electrical Engineering, Czech
Technical University, 1998.
[232] Z. Tronícek and A. Shinohara. The size of subsequence automaton. Theor. Comput. Sci., 341(1–3):379–384, 2005.
[233] K. Tsuruta, S. Inenaga, H. Bannai and M. Takeda. Shortest unique substrings queries in optimal time. In V. Geffert, B. Preneel, B. Rovan, J. Stuller and A. M. Tjoa,
eds., SOFSEM 2014: Theory and Practice of Computer Science: 40th International
Conference on Current Trends in Theory and Practice of Computer Science, Nový
Smokovec, Slovakia, 26–29 January 2014, Proceedings, vol. 8327, Lecture Notes
in Computer Science, pp. 503–513. Springer, 2014.
[234] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260,
1995.
[235] J. van Leeuwen. On the construction of Huffman trees. In ICALP, pp. 382–410,
1976.
[236] J. S. Vitter. Design and analysis of dynamic Huffman codes. J. ACM, 34(4):
825–845, 1987.

308  Литература
[237] N. Vörös. On the complexity measures of symbol-sequences. In A. Iványi, ed.,
Conference of Young Programmers and Mathematicians, pp. 43–50, Budapest,
1984. Faculty of Sciences, Eötvös Loránd University.
[238] B. Walczak. A simple representation of subwords of the Fibonacci word. Inf.
Process. Lett., 110(21):956–960, 2010.
[239] T. A. Welch. A technique for high-performance data compression. IEEE Computer, 17(6):8–19, 1984.
[240] W. A. Wythoff. A modification of the game of Nim. Nieuw Arch. Wisk., 8:199–202,
1907/1909.
[241] I.-H. Yang, C.-P. Huang and K.-M. Chao. A fast algorithm for computing a longest
increasing subsequence. Inf. Process. Lett., 93(5):249–253, 2005.
[242] E. Zalinescu. Shorter strings containing all k-element permutations. Inf. Process.
Lett., 111(12):605–608, 2011.
[243] J. Ziv and A. Lempel. A universal algorithm for sequential data compression.
IEEE Trans. Inf. Theory, 23(3):337–343, 1977.

Предметный указатель

Символы
|| (длина), 13
−1 (обратное слово), 13
£ (алфавитный порядок), 17
£ (лексикографический порядок), 17
≪ (строго меньше), 17
· (произведение), 13
ε (пустое слово), 13
Φ (золотое сечение), 20

A

Автомат сопоставления со строкой, 76

Б
Базовые факторы, 155
Барроуза–Уилера преобразование, 24
Бесквадратная игра, 34
Бесконечное слово, 18
Бойера–Мура алгоритм, 89
Буква, 13

В

alph() (алфавит), 13

Вхождение (фактора), 14

B

Г

Border(), 14
BW(), 24

Граница, 14
Гребень, 193, --">