php regex find substring in substring

Question

I am still playing around for one project with matching words.

Let assume that I have a given string, say maxmuster . Then I want to mark this part of my random word maxs which are in maxmuster in the proper order, like the letters are.

I wil give some examples and then I tell what I already did. Lets keep the string maxmuster. The bold part is the matched one by regex (best would be in php, however could be python, bash, javascript,...)

maxs

Mymaxmuis

Lemu

muster

Of course also m, u, ... will be matched then. I know that, I am going to fix that later. However, the solution, I though, should not so difficult, so I try to divide the word in groups like this:

/(maxmuster)?|(maxmuste)?|(maxmust)?|(maxmus)?|(maxmu)?|(maxm)?|(max)?|(ma)?|(m)?/gui

But then I forgot of course the other combinations, like:

(axmuster)(xmus) and so on. Did I really have to do that, or exist there a simple regex trick, to solve this question, like I explained above?

Thank you very much

Answer 1

Sounds like you need string intersection. If you don't mind non regex idea, have a look in Wikibooks Algorithm Implementation/Strings/Longest common substring PHP section.

foreach(["maxs", "Mymaxmuis", "Lemu", "muster"] AS $str)
  echo get_longest_common_subsequence($str, "maxmuster") . "\n";

max
maxmu
mu
muster

See this PHP demo at tio.run (caseless comparison).

---

If you need a regex idea, I would join both strings with space and use a pattern like this demo.

(?=(\w+)(?=\w* \w*?\1))\w

It will capture inside a lookahead at each position before a word character in the first string the longest substring that also matches the second string. Then by PHP matches of the first group need to be sorted by length and the longest match will be returned. See the PHP demo at tio.run.

function get_longest_common_subsequence($w1="", $w2="")
{
  $test_str = preg_quote($w1,'/')." ".preg_quote($w2,'/');

  if(preg_match_all('/(?=(\w+)(?=\w* \w*?\1))\w/i', $test_str, $out) > 0)
  {
    usort($out[1], function($a, $b) { return strlen($b) - strlen($a); });
    return $out[1][0];
  }
}

Answer 2

TL;DR

Using Regular Expressions:

longestSubstring(['Mymaxmuis', 'axmuis', 'muster'], buildRegexFrom('maxmuster'));

Full snippet

---

Using below regex you are able to match all true sub-strings of string maxmuster:

(?|((?:
    m(?=a)
    |(?<=m)a
    |a(?=x)
    |(?<=a)x
    |x(?=m)
    |(?<=x)m
    |m(?=u)
    |(?<=m)u
    |u(?=s)
    |(?<=u)s
    |s(?=t)
    |(?<=s)t
    |t(?=e)
    |(?<=t)e
    |e(?=r)
    |(?<=e)r
)+)|([maxmuster]))

Live demo

You have to cook such a regex from a word like maxmuster so you need a function to call it:

function buildRegexFrom(string $word): string {
    // Split word to letters
    $letters = str_split($word);
    // Creating all side of alternations in our regex
    foreach ($letters as $key => $letter)
        if (end($letters) != $letter)
            $regex[] = "$letter(?={$letters[$key + 1]})|(?<=$letter){$letters[$key + 1]}";
    // Return whole cooked pattern
    return "~(?|((?>".implode('|', $regex).")+)|([$word]))~i";
}

To return longest match you need to sort results according to matches length from longest to shortest. It means writing another piece of code for it:

function longestSubstring(array $array, string $regex): array {
    foreach ($array as $value) {
        preg_match_all($regex, $value, $matches);
        usort($matches[1], function($a, $b) {
            return strlen($b) <=> strlen($a);
        });
        // Store longest match being sorted
        $substrings[] = $matches[1][0];
    }

    return $substrings;
}

Putting all things together:

print_r(longestSubstring(['Mymaxmuis', 'axmuis', 'muster'], buildRegexFrom('maxmuster')));

Outputs:

Array
(
    [0] => maxmu
    [1] => axmu
    [2] => muster
)

PHP live demo

Answer 3

Here is my take on this problem using regex.

<?php
$subject="maxmuster";
$str="Lemu";

$comb=str_split($subject); // Split into single characters.
$len=strlen($subject);

for ($i=2; $i<=$len; $i++){
    for($start=0; $start<$len; $start++){
        $temp="";
        $inc=$start;
        for($j=0; $j<$i; $j++){
            $temp=$temp.$subject[$inc];
            $inc++;
        }
        array_push($comb,$temp);
    }
}

echo "Matches are:\n";
for($i=0; $i<sizeof($comb); $i++){
    $pattern = "/".$comb[$i]."/";
    if(preg_match($pattern,$str, $matches)){
        print_r($matches);  
    };
}
?>

And here is an Ideone Demo.