Substring counting with insertions

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

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.

• Jezik: Angleški jezik
• Ključne besede: string, substring, counting, insertion, KMP, period, weighted ancestors
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 24 str.
• Številčenje: Vol. 18, iss. 6, art. 371
• PID: 20.500.12556/RUL-172854
• UDK: 004
• ISSN pri članku: 1999-4893
• DOI: 10.3390/a18060371
• COBISS.SI-ID: 240187395
• Datum objave v RUL: 11.09.2025

Gradivo je del revije

• Naslov: Algorithms
• Skrajšan naslov: Algorithms
• Založnik: MDPI
• ISSN: 1999-4893
• COBISS.SI-ID: 517501977

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: niz, podniz, štetje, vstavljanje, KMP, perioda, uteženi predniki

Projekti

• Financer: ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
• Številka projekta: P2-0103
• Naslov: Tehnologije znanja

• Financer: ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
• Številka projekta: P2-0209
• Naslov: Umetna inteligenca in inteligentni sistemi