Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural model that allows for capturing similarities of numerical sequences. Oizumi et al. [CPM 2022] showed that subsequence pattern matching under CT-matching model (CT-MSeq) can be solved in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(nm \log \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>m</mi> <mo>log</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, where n and m are text and pattern lengths, respectively. This current article follows this line of research, and gives the following new results: (1) An O(nm)-time CT-MSeq algorithm for binary alphabets. (2) An <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O((nm)^{1-\epsilon })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo>-</mo> <mi>ϵ</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-time conditional lower bound for the CT-MSeq problem on alphabets of size 4, for any constant <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\epsilon > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, under the Orthogonal Vector Hypothesis (OVH). Further, we introduce the new problem of longest common subsequence under CT-matching (CT-LCS) for two given strings S and T of length n, and present the following results: (3) An <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(n^6)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>6</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-time CT-LCS algorithm for general ordered alphabets. (4) An <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(n^2 / \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-time CT-LCS algorithm for binary alphabets. (5) An <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(n^{2-\epsilon })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>2</mn> <mo>-</mo> <mi>ϵ</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-time conditional lower bound for the CT-LCS problem on alphabets of size 5, for any constant <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\epsilon > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, under OVH.

Subsequence Matching and LCS under Cartesian-Tree Equivalence

期刊论文
发表日期：

2026年2月9日

查看全文

Taketo Tsujimoto,
Yuki Yonemoto,
Hiroki Shibata,
Takuya Mieno,
Yuto Nakashima,
Shunsuke Inenaga

摘要

Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural model that allows for capturing similarities of numerical sequences. Oizumi et al. [CPM 2022] showed that subsequence pattern matching under CT-matching model (CT-MSeq) can be solved in $O(nm \log \log n)$ $O (n m log log n)$ time, where n and m are text and pattern lengths, respectively. This current article follows this line of research, and gives the following new results: (1) An O(nm)-time CT-MSeq algorithm for binary alphabets. (2) An $O((nm)^{1-\epsilon })$ $O ({(n m)}^{1 - ϵ})$ -time conditional lower bound for the CT-MSeq problem on alphabets of size 4, for any constant $\epsilon > 0$ $ϵ > 0$ , under the Orthogonal Vector Hypothesis (OVH). Further, we introduce the new problem of longest common subsequence under CT-matching (CT-LCS) for two given strings S and T of length n, and present the following results: (3) An $O(n^6)$ $O (n^{6})$ -time CT-LCS algorithm for general ordered alphabets. (4) An $O(n^2 / \log n)$ $O (n^{2} / log n)$ -time CT-LCS algorithm for binary alphabets. (5) An $O(n^{2-\epsilon })$ $O (n^{2 - ϵ})$ -time conditional lower bound for the CT-LCS problem on alphabets of size 5, for any constant $\epsilon > 0$ $ϵ > 0$ , under OVH.