如何将包含重复 n 次的相同子字符串的字符串减少为子字符串的单个实例

Question

'ageage'我有像or'feetfeetfeet'或这样的字符串'cmcmcmcmcm'，我想分别将它们减少为'age', 'feet', 和'cm'。这是规范化的中间步骤，用于匹配最初也包含数字的某些类别的数据字段的不同数据源。数字部分已被删除到一个单独的字符串中。所有的 unicode 字母都被音译为小写 ASCII 字母：public static function transliterate(string $value){    $transliterator = Transliterator::createFromRules(        ':: Any-Latin; :: Latin-ASCII; :: NFD; :: [:Nonspacing Mark:] Remove; :: Lower(); :: NFC;',        Transliterator::FORWARD    );    return $transliterator->transliterate($value);}另请注意，复数并不重要，因为虽然我提供的示例是英文的，但该项目主要规范化土耳其语字符串，其中此类单词始终是单数。我希望这可以用正则表达式来完成。虽然我不完全确定如何

Answer 1

我认为非正则表达式没问题。

此方法遍历一半的字符串并尝试查找如果在 str_replace 中使用则不返回任何内容的子字符串。

如果我们发现了，那么我们就知道这是一个重复的词。

$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

Answer 2

• 这看起来类似于查找也是后缀的最长公共前缀。现在，这length - longest prefix which is also a suffix就是您的答案。你可以从这个找到构建前缀后缀表的算法KMP pattern matching algorithm。

• 时间复杂度为O(n)，空间复杂度为O(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));

注意：如果您的字符串格式不正确，例如xyz没有重复的子字符串，您可以使用添加额外的检查str_repeat()并在需要时抛出异常。

Answer 3

我已经想出如何使用正则表达式来做到这一点。尽管我已经意识到它可能对我的目的没有用，因为 mmmm 可以是 2x mm（毫米）或 4x m（米）。虽然如果我只关心最多支持 3 次重复，我可以使用：

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;

}

并不是说下面会把字符串分成最小的重复素数：

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

$repeating = $matches[1];

这是此输出的表格：

┌────────────┬────────────┐

│   $input   │ $repeating │

├────────────┼────────────┤

│ mm         │ m          │

│ mmm        │ m          │

│ mmmm       │ mm         │

│ mmmmm      │ m          │

│ mmmmmm     │ mmm        │

│ mmmmmmm    │ m          │

│ mmmmmmmm   │ mmmm       │

│ mmmmmmmmm  │ mmm        │

│ mmmmmmmmmm │ mmmmm      │

└────────────┴────────────┘

因为只考虑最小的素数细分

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

不合适，因为它会像上表一样，发现 'mmmmmm' 的重复部分是 'mmm' 而不是所需的 mm。

我在开头提供的三个案例实施是我目前正在使用的，因为我的输入通常是产品的年龄组或维度，我还没有看到产品被描述为超过三个维度或年龄组，'11yr,12yr,13yr,14yr'虽然我可以想象像后者这样的事情，无论多么罕见，最终都会发生。因此，我可能会放弃这种方法，转而使用 preg_match_all 从包含数字的原始字符串中提取单位：

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

然而，如果其他人实际上有兴趣找到最小的重复子字符串（所以 'm' 代表 'mmmm'），这可以通过循环中的正则表达式来完成：

$repeating = $input;

while(preg_match('/^([a-z]*)\1+$/', $repeating, $matches)) {

    $repeating = $matches[1];

}

这将产生：

┌────────────┬────────────┐

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

└────────────┴────────────┘

Answer 4

您还可以使用str_split()将字符串转换为数组并找到其唯一元素，然后再次返回将所有唯一元素内爆在一起。

<?php

$str = array_unique(str_split('ageage'));

$result = implode($str);

?>

输出

age