Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions

Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, Takuya Mieno

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

抄録

Let two static sequences of strings P and S, representing prefix and suffix conditions respectively, be given as input for preprocessing. For the query, let two positive integers k1 and k2 be given, as well as a string T given in an online manner, such that Ti represents the length-i prefix of T for 1 ≤ i≤ | T|. In this paper we are interested in computing the set ansi of distinct substrings w of Ti such that k1≤ | w| ≤ k2, and w contains some p∈ P as a prefix and some s∈ S as a suffix. More specifically, the counting problem is to output | ansi|, whereas the reporting problem is to output all elements of ansi, for each iteration i. Let σ denote the alphabet size, and for a sequence of strings A, ‖ A‖ = ∑ uA| u|. Then, we show that after O((‖ P‖ + ‖ S‖ ) log σ) -time preprocessing, the solutions for the counting and reporting problems for each iteration up to i can be output in O(| Ti| log σ) and O(| Ti| log σ+ | ansi| ) total time. The preprocessing time can be reduced to O(‖ P‖ + ‖ S‖ ) for integer alphabets of size polynomial with regard to ‖ P‖ + ‖ S‖. Our algorithms have possible applications to network traffic classification.

本文言語英語
ホスト出版物のタイトルString Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Proceedings
編集者Diego Arroyuelo, Diego Arroyuelo, Barbara Poblete
出版社Springer Science and Business Media Deutschland GmbH
ページ24-37
ページ数14
ISBN(印刷版)9783031206429
DOI
出版ステータス出版済み - 2022
イベント29th International Symposium on String Processing and Information Retrieval, SPIRE 2022 - Concepción, チリ
継続期間: 11月 8 202211月 10 2022

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
13617 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

会議

会議29th International Symposium on String Processing and Information Retrieval, SPIRE 2022
国/地域チリ
CityConcepción
Period11/8/2211/10/22

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル