Page 35 - 2024F

28 UEC Int’l Mini-Conference No.53

g ≤ |v| ≤ G for g, G ∈ N. Another problem is [5] Peter Weiner. “Linear pattern matching
defined as, for each position i in string S, finding algorithms”. In: 14th Annual Symposium
all substrings u 1 vu 2 , u 1 = u 2 where u 2 begins at on Switching and Automata Theory (swat
index i and the gap is constrained by g(i) ≤ 1973). 1973, pp. 1–11. doi: 10.1109/SWAT.
|v| ≤ G(i) for given functions g and G. 1973.13.

5 Acknowledgments

We would like to express our gratitude to Pro-
fessor Hideo Bannai (Institute of Science Tokyo)
and Professor Shunsuke Inenaga (Kyushu Uni-
versity) for their valuable input regarding this
research. Both Professors provided great insight
into the workings of runs and ideas on their
application to the problem of counting gapped
repeats.

References

[1] Hideo Bannai et al. “The “Runs” The-
orem”. In: SIAM Journal on Computing
46.5 (Jan. 2017), pp. 1501–1514. issn: 1095-
7111. doi: 10.1137/15m1011032.
[2] Dan Gusfield. “Algorithms on Strings,
Trees, and Sequences: Computer Science
and Computational Biology”. In: 1997.
url: https : / / api . semanticscholar .
org/CorpusID:263608249.
[3] Andrei Popa and Alexandru Popa. “Ef-
ficient Algorithms for Counting Gapped
Palindromes”. In: 32nd Annual Sympo-
sium on Combinatorial Pattern Matching
(CPM 2021). Ed. by Pawe l Gawrychowski
and Tatiana Starikovskaya. Vol. 191. Leib-
niz International Proceedings in Informat-
ics (LIPIcs). Dagstuhl, Germany: Schloss
Dagstuhl – Leibniz-Zentrum f¨ur Infor-
matik, 2021, 23:1–23:13. isbn: 978-3-95977-
186-3. doi: 10.4230/LIPIcs.CPM.2021.
23.
[4] Esko Ukkonen. “On-line construction of
suffix trees”. In: Algorithmica 14 (1995),
pp. 249–260. url: https : / / api .
semanticscholar . org / CorpusID :
6027556.