Longest (k]-Tuple Common Substrings

Tiantian Li; Haitao Jiang; Lusheng Wang; Daming Zhu

doi:10.1007/978-981-97-7752-5_8

Longest (k]-Tuple Common Substrings

Tiantian Li, Haitao Jiang, Lusheng Wang, Daming Zhu^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

3 Citations (Scopus)

Abstract

A (k]-tuple common substring (abbr. (k]-CSS) is a common subsequence of two or more given strings including at most k common substrings. The complexity of finding a longest (k]-CSS of 2 strings is still open. We present a dynamic programming algorithm for finding a longest (k]-CSS of two strings in O(kn₁n₂) time and space where n₁ and n₂ are the given string lengths. To breakthrough the quadratic space complexity, we present an algorithm for finding a longest (k]-CSS in O(kn₁n₂) time and O(n₁+kn₂) space. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

Original language	English
Title of host publication	Frontiers of Algorithmics
Subtitle of host publication	18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings
Editors	Bo Li, Minming Li, Xiaoming Sun
Publisher	Springer
Pages	106-114
ISBN (Electronic)	978-981-97-7752-5
ISBN (Print)	978-981-97-7751-8
DOIs	https://doi.org/10.1007/978-981-97-7752-5_8
Publication status	Published - 2025
Event	5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024) - Hong Kong Polytechnic University, Hong Kong, China Duration: 29 Jul 2024 → 31 Jul 2024 https://ijtcs2024.comp.polyu.edu.hk/

Publication series

Name	Lecture Notes in Computer Science
Volume	14752
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024)
Place	Hong Kong, China
Period	29/07/24 → 31/07/24
Internet address	https://ijtcs2024.comp.polyu.edu.hk/

Research Keywords

Algorithm
Common substring
Complexity

Access Output

10.1007/978-981-97-7752-5_8

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{5144b2456ea749a3ad9b543780687c7c,

title = "Longest (k]-Tuple Common Substrings",

abstract = "A (k]-tuple common substring (abbr. (k]-CSS) is a common subsequence of two or more given strings including at most k common substrings. The complexity of finding a longest (k]-CSS of 2 strings is still open. We present a dynamic programming algorithm for finding a longest (k]-CSS of two strings in O(kn1n2) time and space where n1 and n2 are the given string lengths. To breakthrough the quadratic space complexity, we present an algorithm for finding a longest (k]-CSS in O(kn1n2) time and O(n1+kn2) space. {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.",

keywords = "Algorithm, Common substring, Complexity",

author = "Tiantian Li and Haitao Jiang and Lusheng Wang and Daming Zhu",

year = "2025",

doi = "10.1007/978-981-97-7752-5_8",

language = "English",

isbn = "978-981-97-7751-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "106--114",

editor = "Bo Li and Minming Li and Xiaoming Sun",

booktitle = "Frontiers of Algorithmics",

note = "5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024) ; Conference date: 29-07-2024 Through 31-07-2024",

url = "https://ijtcs2024.comp.polyu.edu.hk/",

}

Li, T, Jiang, H, Wang, L & Zhu, D 2025, Longest (k]-Tuple Common Substrings. in B Li, M Li & X Sun (eds), Frontiers of Algorithmics: 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings. Lecture Notes in Computer Science, vol. 14752, Springer , pp. 106-114, 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024), Hong Kong, China, 29/07/24. https://doi.org/10.1007/978-981-97-7752-5_8

Longest (k]-Tuple Common Substrings. / Li, Tiantian; Jiang, Haitao; Wang, Lusheng et al.
Frontiers of Algorithmics: 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings. ed. / Bo Li; Minming Li; Xiaoming Sun. Springer , 2025. p. 106-114 (Lecture Notes in Computer Science; Vol. 14752).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Longest (k]-Tuple Common Substrings

AU - Li, Tiantian

AU - Jiang, Haitao

AU - Wang, Lusheng

AU - Zhu, Daming

PY - 2025

Y1 - 2025

N2 - A (k]-tuple common substring (abbr. (k]-CSS) is a common subsequence of two or more given strings including at most k common substrings. The complexity of finding a longest (k]-CSS of 2 strings is still open. We present a dynamic programming algorithm for finding a longest (k]-CSS of two strings in O(kn1n2) time and space where n1 and n2 are the given string lengths. To breakthrough the quadratic space complexity, we present an algorithm for finding a longest (k]-CSS in O(kn1n2) time and O(n1+kn2) space. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

AB - A (k]-tuple common substring (abbr. (k]-CSS) is a common subsequence of two or more given strings including at most k common substrings. The complexity of finding a longest (k]-CSS of 2 strings is still open. We present a dynamic programming algorithm for finding a longest (k]-CSS of two strings in O(kn1n2) time and space where n1 and n2 are the given string lengths. To breakthrough the quadratic space complexity, we present an algorithm for finding a longest (k]-CSS in O(kn1n2) time and O(n1+kn2) space. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

KW - Algorithm

KW - Common substring

KW - Complexity

UR - http://www.scopus.com/inward/record.url?scp=85215321611&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85215321611&origin=recordpage

U2 - 10.1007/978-981-97-7752-5_8

DO - 10.1007/978-981-97-7752-5_8

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-981-97-7751-8

T3 - Lecture Notes in Computer Science

SP - 106

EP - 114

BT - Frontiers of Algorithmics

A2 - Li, Bo

A2 - Li, Minming

A2 - Sun, Xiaoming

PB - Springer

T2 - 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024)

Y2 - 29 July 2024 through 31 July 2024

ER -

Longest (k]-Tuple Common Substrings

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this