php - How to reduce a string containing the same substring repeated n times to a single instace of the substring

Solution:

I assume non regex is ok.

This method loops through half the string and tries to find a substring that if used in a str_replace returns nothing.
If we find that then the know it's a repeating word.

$str = 'feetfeetfeet';
$return = $str; // return full str if it fails

$len = strlen($str);

for($i = 1; $i < $len/2; $i++){
    $sub = substr($str, 0, $i);
    if(str_replace($sub, "", $str) == ""){
        $return = $sub;
        break;
    }
}

echo $return; //feet
Copy code

Solution:

• This looks similar to finding longest common prefix which is also a suffix. Now, thelength - longest prefix which is also a suffix is your answer. You can find the algorithm of building the prefix suffix table from this .

• Time complexity isO(n) and space complexity isO(n).

<?php

$str = "feetfeetfeet";
$length = strlen($str);

$prefix_suffix_table = array_fill(0, $length, 0);

$j = 0;
for($i = 1; $i < $length; ++$i){
    while($j > 0 && $str[$i] != $str[$j]){
        $j = $prefix_suffix_table[$j - 1];
    }

    if($str[$i] == $str[$j]){
        $prefix_suffix_table[$i] = ++$j;
    }
}

echo substr($str, 0, $length - end($prefix_suffix_table));
Copy code

Demo: http://sandbox.onlinephpfunctions.com/code/b401c75cde38a51a561b53bb0a6294eb615b208c

Note: If your string is malformed likexyz which doesn't have a repeating substring, you can just add an additional check usingstr_repeat() and throw an exception if required.

Solution:

You can also usestr_split() to convert the string into array and find its unique elements and then again return implode all the unique elements together.

<?php
$str = array_unique(str_split('ageage'));
$result = implode($str);
?>
Copy code

Output

age
Copy code

Solution:

I have figured out how to do this with a regex. Even though I have realized that it might not be useful for my purposes because mmmm can be both 2x mm (millimeter) or 4x m (meters). Though If I only care about supporting up to 3 repetitions I can use:

if(preg_match('/^([a-z]*)\1{2}$/', $input, $matches)) {
    $repeating = $matches[1];
    $reps = 3;
} elseif(if(preg_match('/^([a-z]*)\1$/', $input, $matches)) {
    $repeating = $matches[1];
    $reps = 2;
} else {
    $repeating = $input;
    $reps = 1;
}
Copy code

Not that the following will divide the string into the smallest prime number of repeats:

preg_match('/^([a-z]*)\1+$/', $input, $matches);
$repeating = $matches[1];
Copy code

Here is a table of the outputs of this:

?�??�??�??�??�??�??�??�??�??�??�??�??�??��?�??�??�??�??�??�??�??�??�??�??�??�??�?
?��   $input   ?�� $repeating ?��
?�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??��
?�� mm         ?�� m          ?��
?�� mmm        ?�� m          ?��
?�� mmmm       ?�� mm         ?��
?�� mmmmm      ?�� m          ?��
?�� mmmmmm     ?�� mmm        ?��
?�� mmmmmmm    ?�� m          ?��
?�� mmmmmmmm   ?�� mmmm       ?��
?�� mmmmmmmmm  ?�� mmm        ?��
?�� mmmmmmmmmm ?�� mmmmm      ?��
?��?�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�?
Copy code

Because only the smalles prime subdivisions are considered

preg_match('/^([a-z]*)\1{1,2}$/', $input, $matches)
Copy code

is unsuitable as it will, like in the above table, find the repeating part of 'mmmmmm' to be 'mmm' instead of the desired mm.

The three case implementation I have provided at the beginning is what I am currently using because my input is generally either age groups or dimensions for products and I have yet to see a product be described with more than three dimensions or with an age group like'11yr,12yr,13yr,14yr' though I can imagine something like the latter, however rare, eventually occurring. Thus I will probably move away from this method and switch to extracting the units from the original string containing the numbers with preg_match_all:

preg_match_all('/([0-9]+)\s*([a-z]*)\s*/', $input, $matches)
Copy code

However in case someone else is actually interested in finding the smallest repeating substring (so 'm' for 'mmmm') this can be done with a regex in a loop:

$repeating = $input;
while(preg_match('/^([a-z]*)\1+$/', $repeating, $matches)) {
    $repeating = $matches[1];
}
Copy code

This will produce:

?�??�??�??�??�??�??�??�??�??�??�??�??�??��?�??�??�??�??�??�??�??�??�??�??�??�??�?
?��   $input   ?�� $repeating ?��
?�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??��
?�� mm         ?�� m          ?��
?�� mmm        ?�� m          ?��
?�� mmmm       ?�� m          ?��
?�� mmmmm      ?�� m          ?��
?�� mmmmmm     ?�� m          ?��
?�� mmmmmmm    ?�� m          ?��
?�� mmmmmmmm   ?�� m          ?��
?�� mmmmmmmmm  ?�� m          ?��
?�� mmmmmmmmmm ?�� m          ?��
?�� cmcm       ?�� cm         ?��
?�� cmcmcm     ?�� cm         ?��
?�� cmcmcmcm   ?�� cm         ?��
?�� cmcmcmcmcm ?�� cm         ?��
?��?�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�??�?
Copy code