# What algorithm will determine if two strings match eachother or not?

$$\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

• Terminology: I would not say that IOWA is a substring of IOWHAIO. Sep 6, 2022 at 16:03
• I agree with @YvesDaoust, did you perhaps mean "subsequence" instead of "substring"? Sep 6, 2022 at 17:23
• 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.
– D.W.
Sep 6, 2022 at 22:48
• 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).
– D.W.
Sep 6, 2022 at 22:49
• In which course is this an exercise? Sep 7, 2022 at 11:03