1
$\begingroup$

Given finite sets $A,B,C$ of finite strings, does there exist some $x,y \in A$ and some $z$ such that $x.z \in B$ and $y.z \in C$ hold (where $x.z$ denotes the concatenation of $x$ and $z$)? That is, do $B$ and $C$ contain a pair of sequences with a common suffix such that the respective remaining prefixes are both contained in $A$?

For example, $A := \{a,b,cd\}$, $B := \{ae,ada\}$, $C := \{bd,cdda\}$ satisfy the above condition for $a, cd \in A$, $ada \in B$, and $cdda \in C$.

Does this problem have an established name?

$\endgroup$
3
  • $\begingroup$ Even the problem with a single prefix in $A$ does not seem to have a name. You might call it a "prefix.suffix search", though the dot as a concatenation operator is not universal. Or "concatenation search". Or conversely, a "split string search" or "split string match" ? $\endgroup$
    – Yves Daoust
    Mar 9, 2022 at 10:21
  • $\begingroup$ Your variant would be a "2,1-concatenation search". $\endgroup$
    – Yves Daoust
    Mar 9, 2022 at 10:24
  • $\begingroup$ You can address this problem by performing a suffix search for all elements of $B$ in $C$. Then for every matching subsets, check for at least two elements in the intersection with $A$. $\endgroup$
    – Yves Daoust
    Mar 9, 2022 at 10:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.