Substring counting with insertions

Brank, Janez (author), Hočevar, Tomaž (author)

Substring counting is a classical algorithmic problem with numerous solutions that achieve linear time complexity. In this paper, we address a variation of the problem where, given three strings p, t, and s, we are interested in the number of occurrences of p in all strings that would result from inserting t into s at every possible position. Essentially, we are solving several substring counting problems of the same substring p in related strings. We give a detailed description of several conceptually different approaches to solving this problem and conclude with an algorithm that has a linear time complexity. The solution is based on a recent result from the field of substring search in compressed sequences and exploits the periodicity of strings. We also provide a self-contained implementation of the algorithm in C++ and experimentally verify its behavior, chiefly to demonstrate that its running time is linear in the lengths of all three input strings.

• Language: English
• Keywords: string, substring, counting, insertion, KMP, period, weighted ancestors
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: 24 str.
• Numbering: Vol. 18, iss. 6, art. 371
• PID: 20.500.12556/RUL-172854
• UDC: 004
• ISSN on article: 1999-4893
• DOI: 10.3390/a18060371
• COBISS.SI-ID: 240187395
• Publication date in RUL: 11.09.2025

Record is a part of a journal

• Title: Algorithms
• Shortened title: Algorithms
• Publisher: MDPI
• ISSN: 1999-4893
• COBISS.SI-ID: 517501977

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: niz, podniz, štetje, vstavljanje, KMP, perioda, uteženi predniki

Projects

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P2-0103
• Name: Tehnologije znanja

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P2-0209
• Name: Umetna inteligenca in inteligentni sistemi