如何将包含重复 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++){&nbsp; &nbsp; $sub = substr($str, 0, $i);&nbsp; &nbsp; if(str_replace($sub, "", $str) == ""){&nbsp; &nbsp; &nbsp; &nbsp; $return = $sub;&nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; }}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)) {&nbsp; &nbsp; $repeating = $matches[1];&nbsp; &nbsp; $reps = 3;} elseif(if(preg_match('/^([a-z]*)\1$/', $input, $matches)) {&nbsp; &nbsp; $repeating = $matches[1];&nbsp; &nbsp; $reps = 2;} else {&nbsp; &nbsp; $repeating = $input;&nbsp; &nbsp; $reps = 1;}并不是说下面会把字符串分成最小的重复素数：preg_match('/^([a-z]*)\1+$/', $input, $matches);$repeating = $matches[1];这是此输出的表格：┌────────────┬────────────┐│&nbsp; &nbsp;$input&nbsp; &nbsp;│ $repeating │├────────────┼────────────┤│ mm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;│ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmm&nbsp; &nbsp; &nbsp; &nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmm&nbsp; &nbsp; &nbsp; &nbsp;│ mm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;││ mmmmm&nbsp; &nbsp; &nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmm&nbsp; &nbsp; &nbsp;│ mmm&nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmm&nbsp; &nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmmm&nbsp; &nbsp;│ mmmm&nbsp; &nbsp; &nbsp; &nbsp;││ mmmmmmmmm&nbsp; │ mmm&nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmmmmm │ mmmmm&nbsp; &nbsp; &nbsp; │└────────────┴────────────┘因为只考虑最小的素数细分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)) {&nbsp; &nbsp; $repeating = $matches[1];}这将产生：┌────────────┬────────────┐│&nbsp; &nbsp;$input&nbsp; &nbsp;│ $repeating │├────────────┼────────────┤│ mm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;│ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmm&nbsp; &nbsp; &nbsp; &nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmm&nbsp; &nbsp; &nbsp; &nbsp;│ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmm&nbsp; &nbsp; &nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmm&nbsp; &nbsp; &nbsp;│ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmm&nbsp; &nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmmm&nbsp; &nbsp;│ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmmmm&nbsp; │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ mmmmmmmmmm │ m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ││ cmcm&nbsp; &nbsp; &nbsp; &nbsp;│ cm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;││ cmcmcm&nbsp; &nbsp; &nbsp;│ cm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;││ cmcmcmcm&nbsp; &nbsp;│ cm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;││ cmcmcmcmcm │ cm&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;│└────────────┴────────────┘

Answer 4

您还可以使用str_split()将字符串转换为数组并找到其唯一元素，然后再次返回将所有唯一元素内爆在一起。<?php$str = array_unique(str_split('ageage'));$result = implode($str);?>输出age