Scholarlink

<p>A subsequence of a string <i>T</i> is any string that can be obtained by removing zero or more symbols from <i>T</i>. The paper deals with the Window Accumulated Subsequence matching Problem (WASP), which is defined as follows: Given two strings, the text <i>T</i> and the pattern <i>P</i>, and a positive integer <i>w</i>, the window size, find the number of size <i>w</i> substrings of <i>T</i> that contain <i>P</i> as a subsequence. Three algorithms for this problem are introduced: a bit-parallel approach, an algorithm preprocessing the pattern, and an algorithm preprocessing the text. The bit-parallel approach outperforms the state-of-the-art algorithm, and the other two algorithms outperform the bit-parallel approach for small alphabets, short patterns, and windows that are not much larger than the pattern. Furthermore, a preprocessing of the text that solves WASP for a fixed window size and each possible pattern of a given size is described. This is beneficial when we are to solve WASP for a single text and multiple patterns, because when the text is preprocessed, a solution is provided promptly.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Fast algorithms for window accumulated subsequence matching problem

  • 期刊论文

  • 发表日期：

    2026年2月25日

查看全文
  • Zdenek Tronicek

摘要

A subsequence of a string T is any string that can be obtained by removing zero or more symbols from T. The paper deals with the Window Accumulated Subsequence matching Problem (WASP), which is defined as follows: Given two strings, the text T and the pattern P, and a positive integer w, the window size, find the number of size w substrings of T that contain P as a subsequence. Three algorithms for this problem are introduced: a bit-parallel approach, an algorithm preprocessing the pattern, and an algorithm preprocessing the text. The bit-parallel approach outperforms the state-of-the-art algorithm, and the other two algorithms outperform the bit-parallel approach for small alphabets, short patterns, and windows that are not much larger than the pattern. Furthermore, a preprocessing of the text that solves WASP for a fixed window size and each possible pattern of a given size is described. This is beneficial when we are to solve WASP for a single text and multiple patterns, because when the text is preprocessed, a solution is provided promptly.