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

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ Terminology: I would not say that IOWA is a substring of IOWHAIO. $\endgroup$
    – Yves Daoust
    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$
    – reinierpost
    Sep 7, 2022 at 11:03

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.