20.500.12556/RUL-172854 Substring counting with insertions 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. string substring counting insertion KMP period weighted ancestors niz podniz štetje vstavljanje KMP perioda uteženi predniki true false true Angleški jezik Slovenski jezik Članek v reviji 2025-09-11 14:46:35 2025-09-11 14:46:36 2025-10-25 04:09:30 0000-00-00 00:00:00 2025 0 0 24 str. iss. 6, art. 371 Vol. 18 Jun. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004 1999-4893 10.3390/a18060371 240187395 RAZ_Brank_Janez_2025.pdf RAZ_Brank_Janez_2025.pdf 1 BEEFC68BD0E806068ACD68AE793B16E7 816607727bf3b64b32a429a331894d3ef14ea3e8f0b88e84c0e93ca1106cfb48 97eb1251-8f0d-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=216972 https://www.mdpi.com/1999-4893/18/6/371 1 3128d5d8-8f0d-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=216971 Fakulteta za računalništvo in informatiko 0 0 0