0
$\begingroup$

$\require{enclose}$

Definition of parent

For any three strings $x$, $y$, and $p$, we say that $p$ is a parent of $x$ and $y$ if and only if all of the following:

  • $p$ is a $\enclose{updiagonalstrike, downdiagonalstrike}{\text{substring}}$ sub-sequence of some permutation of the concatenation of $x$ and $y$.
  • $x$ is a $\enclose{updiagonalstrike, downdiagonalstrike}{\text{substring}}$ sub-sequence of $p$
  • $y$ is a $\enclose{updiagonalstrike, downdiagonalstrike}{\text{substring}}$ sub-sequence of $p$

Definition of Match

For any two strings $x$ and $y$, we say that $x$ and $y$ match if and only if no permutation of the shortest length parent of $x$ and $y$ is a parent of $x$ and $y$.

Example One

For example, the following two strings $\enclose{updiagonalstrike, downdiagonalstrike}{\text{math}}$ (Edit: actually, they do NOT match):

  • string 1 "ABC INDUST INC"
  • string 2 "ABC INDUSTRIES"

The following are all examples of minimum-length parent strings:

  • "ABC INDUST RINCES"
  • "ABC INDUSTR INCES"
  • "ABC INDUST RINCES"
  • "ABC INDUST RIESNC"

Example Two

The following two strings do NOT match:

  • string 3 "IOWA"
  • string 4 "OHIO"

One example of a minimum-length common super-sequence is "IOWHAIO".

Unfortunately, if we swap the letter "W" with the letter "H" then we have a new string which is also common super-sequence of "IOWA" and "OHIO"

If any permutation of a minimum length parent string is also a parent string, then the two child strings do not match.

Two strings match each-other if and only if the minimum length parent string is unique.


What is an example of an algorithm which will determine if two strings match each-other or not?

As input, the algorithm accepts an ordered pair of two strings.

The output of the algorithm is a boolean, true or false.


An answer to this question could simply be the name of an algorithm provided that there exists a Wikipedia page on that algorithm. Otherwise your answer should be code or pseudo-code.

Any algorithm which gets the job done is a valid answer to this question. However, an efficient algorithm is likely to garner more up votes than an inefficient one.


For any two strings $x$ and $y$ we define a good parent of $x$ and $y$ to be any super-string of $x$ and $y$ such that no permutation of the good parent is a super-string of $x$ and no permutation of the goof parent is a super string of $y$.

Strings $x$ and $y$ match if and only if there exists a good parent of $x$ and $y$.


EDIT: Everywhere I wrote "sub-string" I should have written "sub-sequence"


We do not want to use the Levenstien Distance


$\endgroup$
10
  • 3
    $\begingroup$ Terminology: I would not say that IOWA is a substring of IOWHAIO. $\endgroup$
    – user16034
    Sep 6, 2022 at 16:03
  • $\begingroup$ I agree with @YvesDaoust, did you perhaps mean "subsequence" instead of "substring"? $\endgroup$
    – Nathaniel
    Sep 6, 2022 at 17:23
  • $\begingroup$ Your definition of 'match' implicitly assumes that every pair of strings $x,y$ has a unique shortest length parent, but this is false: consider two strings $x=$"HI", $y=$"LO", which have two shortest length parents, "HILO" and "LIHO". Please edit your definition to revise the definition of 'match' to clarify what to do in this kind of situation. $\endgroup$
    – D.W.
    Sep 6, 2022 at 22:48
  • $\begingroup$ Your definition of 'match' can't be right. The identity permutation is a permutation, so it is impossible to satisfy the criterion "no permutation of the shortest length parent of x and y is a parent of x and y". There always exists such a permutation (indeed, the identity permutation qualifies). $\endgroup$
    – D.W.
    Sep 6, 2022 at 22:49
  • $\begingroup$ In which course is this an exercise? $\endgroup$ Sep 7, 2022 at 11:03

0

Your Answer

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