PHP – Как вы находите дубликаты групп значений в массиве

Массивы символов – это просто строки. Regex является королем сопоставления строк. Добавьте рекурсию, и решение довольно элегантно, даже с преобразованием взад и вперед от массивов символов:

 function findPattern($str){ $results = array(); if(is_array($str)){ $str = implode($str); } if(strlen($str) == 0){ //reached the end return $results; } if(preg_match_all('/^(.+)\1+(.*?)$/',$str,$matches)){ //pattern found $results[] = array('number' => (strlen($str) - strlen($matches[2][0])) / strlen($matches[1][0]), 'values' => str_split($matches[1][0])); return array_merge($results,findPattern($matches[2][0])); } //no pattern found $results[] = array('number' => 1, 'values' => array(substr($str, 0, 1))); return array_merge($results,findPattern(substr($str, 1))); } 

Вы можете протестировать здесь: https://eval.in/507818 и https://eval.in/507815

Если с и d можно сгруппировать, это мой код:

 <?php $array = array( 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'c', 'd', ); $res = array(); foreach ($array AS $value) { if (!isset($res[$value])) { $res[$value] = 0; } $res[$value]++; } foreach ($res AS $key => $value) { $fArray[$value][] = $key; for ($i = $value - 1; $i > 0; $i--) { $fArray[$i][] = $key; } } $res = array(); foreach($fArray AS $key => $value) { if (!isset($res[serialize($value)])) { $res[serialize($value)] = 0; } $res[serialize($value)]++; } $fArray = array(); foreach($res AS $key => $value) { $fArray[] = array('number' => $value, 'values' => unserialize($key)); } echo '<pre>'; var_dump($fArray); echo '</pre>'; 

Конечным результатом является:

 array (size=2) 0 => array (size=2) 'number' => int 2 'values' => array (size=4) 0 => string 'a' (length=1) 1 => string 'b' (length=1) 2 => string 'c' (length=1) 3 => string 'd' (length=1) 1 => array (size=2) 'number' => int 1 'values' => array (size=2) 0 => string 'c' (length=1) 1 => string 'd' (length=1) 

Следующий код вернет ожидаемый результат, найдя самые длинные порции с повторяющимися значениями:

 function pepito($array) { $sz=count($array); $patterns=Array(); for ($pos=0;$pos<$sz;$pos+=$len) { $nb=1; for ($len=floor($sz/2);$len>0;$len--) { while (array_slice($array, $pos, $len)==array_slice($array, $pos+$len, $len)) { $pos+=$len; $nb++; } if ($nb>1) break; } if (!$len) $len=1; $patterns[]=Array('number'=>$nb, 'values'=>array_slice($array, $pos, $len)); } return $patterns; } 

Это будет соответствовать вашим примерам:

{['a', 'b', 'c', 'd'], ['a', 'b', 'c', 'd']}, ['c', 'd']

или {['x'], ['x']}, ['y'], {['x', 'b'], ['x', 'b']}, ['a']

Трудная часть – это больше о таких примерах, как:

{['one', 'one', 'two'], ['one', 'one', 'two']}

Или самый сложный выбор:

один, два, один, два, один, два, один, два

Потому что мы можем сгруппировать это как в форме:

[один, два], [один, два], [один, два], [один, два]

[один, два, один, два], [один, два, один, два]

где нет «очевидного» выбора. Мой вышеприведенный алгоритм всегда будет рассматривать самое длинное совпадение, так как это самая простая реализация для рассмотрения любой комбинации.

EDIT: вы также должны рассмотреть случаи, когда самое длинное совпадение происходит после более короткого :

Пример:

«один», «два», «один», «два», «три», «четыре», «один», «два», «три»,

Если вы начинаете слева направо, вы можете группировать как:

{['one', 'two'], ['one', 'two'],} 'three', 'four', 'one', 'two', 'three', 'four'

когда вы можете группировать, как:

«один», «два», «один», «два», «три», «четыре», «один», «два», «три», «четыре»)

Эта ситуация должна быть решена с помощью рекурсивных вызовов, чтобы получить лучшее решение, но это приведет к увеличению времени выполнения:

 function pepito($array) { if (($sz=count($array))<1) return Array(); $pos=0; $nb=1; for ($len=floor($sz/2);$len>0;$len--) { while (array_slice($array, $pos, $len)==array_slice($array, $pos+$len, $len)) { $pos+=$len; $nb++; } if ($nb>1) break; } if (!$len) $len=1; $rec1=pepito(array_slice($array, $pos+$len)); $rec2=pepito(array_slice($array, 1)); if (count($rec1)<count($rec2)+1) { return array_merge(Array(Array('number'=>$nb, 'values'=>array_slice($array, $pos, $len))), $rec1); } return array_merge(Array(Array('number'=>1, 'values'=>array_slice($array, 0, 1))), $rec2); } 

Хорошо, вот мой прием, код ниже разбивает весь исходный массив на самые длинные смежные неперекрывающиеся куски.

Поэтому в такой ситуации

 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'd' [ ] [ ] [ ] [ ] <-- use 2 long groups [ ] [ ] [ ] [ ] [ ] [ ] <-- and not 4 short 

он предпочтет 2 длинные группы для 4 коротких групп.

Обновление: также проверено с примерами из другого ответа, также работает для этих случаев:

 one, two, one, two, one, two, one, two [one two one two], [one two one two] 'one' 'two' 'one' 'two' 'three' 'four' 'one' 'two' 'three' 'four' ['one'] ['two'] ['one' 'two' 'three' 'four'] ['one' 'two' 'three' 'four'] 

Вот код и тесты:

 <?php /* * Splits an $array into chunks of $chunk_size. * Returns number of repeats, start index and chunk which has * max number of ajacent repeats. */ function getRepeatCount($array, $chunk_size) { $parts = array_chunk($array, $chunk_size); $maxRepeats = 1; $maxIdx = 0; $repeats = 1; $len = count($parts); for ($i = 0; $i < $len-1; $i++) { if ($parts[$i] === $parts[$i+1]) { $repeats += 1; if ($repeats > $maxRepeats) { $maxRepeats = $repeats; $maxIdx = $i - ($repeats-2); } } else { $repeats = 1; } } return array($maxRepeats, $maxIdx*$chunk_size, $parts[$maxIdx]); } /* * Finds longest pattern in the $array. * Returns number of repeats, start index and pattern itself. */ function findLongestPattern($array) { $len = count($array); for ($window = floor($len/2); $window >= 1; $window--) { $num_chunks = ceil($len/$window); for ($i = 0; $i < $num_chunks; $i++) { list($repeats, $idx, $pattern) = getRepeatCount( array_slice($array, $i), $window ); if ($repeats > 1) { return array($repeats, $idx+$i, $pattern); } } } return array(1, 0, [$array[0]]); } /* * Splits $array into longest adjacent non-overlapping parts. */ function splitToPatterns($array) { if (count($array) < 1) { return $array; } list($repeats, $start, $pattern) = findLongestPattern($array); $end = $start + count($pattern) * $repeats; return array_merge( splitToPatterns(array_slice($array, 0, $start)), array( array('number'=>$repeats, 'values' => $pattern) ), splitToPatterns(array_slice($array, $end)) ); } 

тесты:

 function isEquals($expected, $actual) { $exp_str = json_encode($expected); $act_str = json_encode($actual); $equals = $exp_str === $act_str; if (!$equals) { echo 'Equals check failed'.PHP_EOL; echo 'expected: '.$exp_str.PHP_EOL; echo 'actual : '.$act_str.PHP_EOL; } return $equals; } assert(isEquals( array(1, 0, ['a']), getRepeatCount(['a','b','c'], 1) )); assert(isEquals( array(1, 0, ['a']), getRepeatCount(['a','b','a','b','c'], 1) )); assert(isEquals( array(2, 0, ['a','b']), getRepeatCount(['a','b','a','b','c'], 2) )); assert(isEquals( array(1, 0, ['a','b','a']), getRepeatCount(['a','b','a','b','c'], 3) )); assert(isEquals( array(3, 0, ['a','b']), getRepeatCount(['a','b','a','b','a','b','a'], 2) )); assert(isEquals( array(2, 2, ['a','c']), getRepeatCount(['x','c','a','c','a','c'], 2) )); assert(isEquals( array(1, 0, ['x','c','a']), getRepeatCount(['x','c','a','c','a','c'], 3) )); assert(isEquals( array(2, 0, ['a','b','c','d']), getRepeatCount(['a','b','c','d','a','b','c','d','c','d'],4) )); assert(isEquals( array(2, 2, ['a','c']), findLongestPattern(['x','c','a','c','a','c']) )); assert(isEquals( array(1, 0, ['a']), findLongestPattern(['a','b','c']) )); assert(isEquals( array(2, 2, ['c','a']), findLongestPattern(['a','b','c','a','c','a']) )); assert(isEquals( array(2, 0, ['a','b','c','d']), findLongestPattern(['a','b','c','d','a','b','c','d','c','d']) )); // Find longest adjacent non-overlapping patterns assert(isEquals( array( array('number'=>1, 'values'=>array('a')), array('number'=>1, 'values'=>array('b')), array('number'=>1, 'values'=>array('c')), ), splitToPatterns(['a','b','c']) )); assert(isEquals( array( array('number'=>1, 'values'=>array('a')), array('number'=>1, 'values'=>array('b')), array('number'=>2, 'values'=>array('c','a')), ), splitToPatterns(['a','b','c','a','c','a']) )); assert(isEquals( array( array('number'=>2, 'values'=>array('a','b','c','d')), array('number'=>1, 'values'=>array('c')), array('number'=>1, 'values'=>array('d')), ), splitToPatterns(['a','b','c','d','a','b','c','d','c','d']) )); /* 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', 'd', */ /* [ ] [ ] [ ] [ ] */ /* NOT [ ] [ ] [ ] [ ] [ ] [ ] */ assert(isEquals( array( array('number'=>2, 'values'=>array('a','b','a','b')), array('number'=>1, 'values'=>array('c')), array('number'=>1, 'values'=>array('d')), ), splitToPatterns(['a','b','a','b','a','b','a','b','c','d']) )); /* 'x', 'x', 'y', 'x', 'b', 'x', 'b', 'a' */ /* // [ ] [ ] [ ] [ ] [ ] [ ] */ assert(isEquals( array( array('number'=>2, 'values'=>array('x')), array('number'=>1, 'values'=>array('y')), array('number'=>2, 'values'=>array('x','b')), array('number'=>1, 'values'=>array('a')), ), splitToPatterns(['x','x','y','x','b','x','b','a']) )); // one, two, one, two, one, two, one, two // [ ] [ ] assert(isEquals( array( array('number'=>2, 'values'=>array('one', 'two', 'one', 'two')), ), splitToPatterns(['one', 'two', 'one', 'two', 'one', 'two', 'one', 'two']) )); // 'one', 'two', 'one', 'two', 'three', 'four', 'one', 'two', 'three', 'four' // [ ] [ ] [ ] [ ] assert(isEquals( array( array('number'=>1, 'values'=>array('one')), array('number'=>1, 'values'=>array('two')), array('number'=>2, 'values'=>array('one','two','three','four')), ), splitToPatterns(['one', 'two', 'one', 'two', 'three', 'four', 'one', 'two', 'three','four']) )); /* 'a', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', */ /* [ ] [ ] [ ] [ ] */ assert(isEquals( array( array('number'=>1, 'values'=>array('a')), array('number'=>2, 'values'=>array('a','b','a','b')), array('number'=>1, 'values'=>array('c')), ), splitToPatterns(['a','a','b','a','b','a','b','a','b','c']) )); /* 'a', 'b', 'a', 'b', 'c', 'd', 'a', 'b', 'a', 'b', 'a', 'b' */ // [ ] [ ] [ ] [ ] [ ] [ ] [ ] assert(isEquals( array( array('number'=>2, 'values'=>array('a', 'b')), array('number'=>1, 'values'=>array('c')), array('number'=>1, 'values'=>array('d')), array('number'=>3, 'values'=>array('a','b')), ), splitToPatterns(['a', 'b', 'a', 'b', 'c', 'd', 'a', 'b', 'a', 'b', 'a', 'b']) )); /* 'a', 'c', 'd', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'c', */ /* [ ] [ ] [ ] [ ] [ ] [ ] */ assert(isEquals( array( array('number'=>1, 'values'=>array('a')), array('number'=>2, 'values'=>array('a','b','a','b')), array('number'=>1, 'values'=>array('c')), ), splitToPatterns(['a','a','b','a','b','a','b','a','b','c']) )); 

Определения :

База шаблонов : последовательность элементов, которые повторяются внутри шаблона. (т. е. для [a, b, a, b, c], [a, b] – основа шаблона, а [a, b, a, b] – шаблон.

Мы хотим начать поиск самой длинной базы шаблонов, а затем следующей самой длинной и т. Д. Важно понимать, что если мы найдем шаблон, нам не нужно проверять его в начале другого шаблона с базой той же длины.

Вот доказательство.

Предположим, что A является базой шаблонов и что мы столкнулись с шаблоном AA. Предположим, что B – другое основание шаблона той же длины, которое формирует шаблон, начинающийся в пределах A. Пусть Y – перекрывающиеся элементы. Если A = XY, то AA = XYXY. Так как B – одна и та же длина, то это должно быть в том случае, когда B = YX, потому что для завершения B мы должны использовать остальные элементы в A. Более того, так как B образует шаблон, мы должны иметь BB, то есть YXYX. Так как A начинается до B, мы имеем XYXYX = AAX = XBB. Если B снова повторится, мы будем иметь XBBB = XYXYXYX = AAAX. Поэтому B не может повторить дополнительное время без повторения A дополнительного времени. Таким образом, нам не нужно проверять более длинные шаблоны в пределах, сгенерированных A.

Самый длинный шаблон может состоять из половины элементов во всем списке, потому что простейший шаблон может происходить ровно в два раза. Таким образом, мы можем начать проверять образцы на половину длины и проделать свой путь до шаблонов размера 2.

Предполагая, что мы ищем массив слева направо, если шаблон найден, нам нужно только искать по обе стороны от него дополнительные шаблоны. Слева нет шаблонов с основаниями одинаковой длины, или они были бы обнаружены заранее. Таким образом, мы ищем левую сторону шаблонов, используя следующий минимальный размер базы. Элементы справа от шаблона не были обысканы, поэтому мы продолжаем поиск шаблонов с использованием базы того же размера.

Функция для этого заключается в следующем:

 function get_patterns($arr, $len = null) { // The smallest pattern base length for which a pattern can be found $minlen = 2; // No pattern base length was specified if ($len === null) { // Use the longest pattern base length possible $maxlen = floor(count($arr) / 2); return get_patterns($arr, $maxlen); // Base length is too small to find any patterns } else if ($len < $minlen) { // Compile elements into lists consisting of one element $results = array(); $num = 1; $elem = $arr[0]; for ($i=1; $i < count($arr); $i++) { if ($elem === $arr[$i]) { $num++; } else { array_push($results, array( 'number' => $num, 'values' => array( $elem ) )); $num = 1; $elem = $arr[$i]; } } array_push($results, array( 'number' => $num, 'values' => array( $elem ) )); return $results; } // Cycle through elements until there aren't enough elements to fit // another repition. for ($i=0; $i < count($arr) - $len * 2 + 1; $i++) { // Number of times pattern base occurred $num_read = 1; // One means there is no pattern yet // Current pattern base we are attempting to match against $base = array_slice($arr, $i, $len); // Check for matches using segments of the same length for the elements // following the current pattern base for ($j = $i + $len; $j < count($arr) - $len + 1; $j += $len) { // Elements being compared to pattern base $potential_match = array_slice($arr, $j, $len); // Match found if (has_same_elements($base, $potential_match)) { $num_read++; // NO match found } else { // Do not check again using currently selected elements break; } } // Patterns were encountered if ($num_read > 1) { // The total number of elements that make up the pattern $pattern_len = $num_read * $len; // The elements before the pattern $before = array_slice($arr, 0, $i); // The elements after the pattern $after = array_slice( $arr, $i + $pattern_len, count($arr) - $pattern_len - $i ); $results = array_merge( // Patterns of a SMALLER length may exist beforehand count($before) > 0 ? get_patterns($before, $len-1) : array(), // Patterns that were found array( array( 'number' => $num_read, 'values' => $base ) ), // Patterns of the SAME length may exist afterward count($after) > 0 ? get_patterns($after, $len) : array() ); return $results; } } // No matches were encountered // Search for SMALLER patterns return get_patterns($arr, $len-1); } 

Функция has_same_elements , которая использовалась для проверки идентичности массивов с примитивными ключами, выглядит следующим образом:

 // Returns true if two arrays have the same elements. // // Precondition: Elements must be primitive data types (ie. int, string, etc) function has_same_elements($a1, $a2) { // There are a different number of elements if (count($a1) != count($a2)) { return false; } for ($i=0; $i < count($a1); $i++) { if ($a1[$i] !== $a2[$i]) { return false; } } return true; } 

Чтобы ускорить работу кода, есть несколько вещей, которые вы могли бы сделать. Вместо того, чтобы нарезать массив, вы можете поставить функцию с индексами в начальную и конечную позиции, которые должны быть исследованы, вместе с массивом. Кроме того, использование строк может быть медленным, поэтому вы можете создать массив, который отображает строки в числа и наоборот. Затем вы можете преобразовать массив строк в массив чисел и использовать его вместо этого. После того, как вы получите результат, вы можете преобразовать массивы чисел обратно в строки.

Я проверил функцию, используя следующий код:

 $tests = array( 'a,b,c,d', 'a', 'a,a,a,a', 'a,a,a,a,a', 'a,a,a,a,a,a', 'b,a,a,a,a,c', 'b,b,a,a,a,a,c,c', 'b,b,a,a,d,a,a,c,c', 'a,b,c,d,a,b,c,d,c,d', 'x,x,y,x,b,x,b,a' ); echo '<pre>'; foreach ($tests as $test) { echo '<div>'; $arr = explode(',',$test); echo "$test<br /><br />"; pretty_print(get_patterns($arr)); echo '</div><br />'; } echo '</pre>'; 

Функция, которую я использовал для печати вывода, pretty_print выглядит следующим образом:

 function pretty_print($results) { foreach ($results as $result) { $a = "array('" . implode("','", $result['values']) . "')"; echo "array('number' => ${result['number']}, 'values' => $a)<br />"; } } 

Результат тестового кода выглядит следующим образом:

 a,b,c,d array('number' => 1, 'values' => array('a')) array('number' => 1, 'values' => array('b')) array('number' => 1, 'values' => array('c')) array('number' => 1, 'values' => array('d')) a array('number' => 1, 'values' => array('a')) a,a,a,a array('number' => 2, 'values' => array('a','a')) a,a,a,a,a array('number' => 2, 'values' => array('a','a')) array('number' => 1, 'values' => array('a')) a,a,a,a,a,a array('number' => 2, 'values' => array('a','a','a')) b,a,a,a,a,c array('number' => 1, 'values' => array('b')) array('number' => 2, 'values' => array('a','a')) array('number' => 1, 'values' => array('c')) b,b,a,a,a,a,c,c array('number' => 2, 'values' => array('b')) array('number' => 2, 'values' => array('a','a')) array('number' => 2, 'values' => array('c')) b,b,a,a,d,a,a,c,c array('number' => 2, 'values' => array('b')) array('number' => 2, 'values' => array('a')) array('number' => 1, 'values' => array('d')) array('number' => 2, 'values' => array('a')) array('number' => 2, 'values' => array('c')) a,b,c,d,a,b,c,d,c,d array('number' => 2, 'values' => array('a','b','c','d')) array('number' => 1, 'values' => array('c')) array('number' => 1, 'values' => array('d')) x,x,y,x,b,x,b,a array('number' => 2, 'values' => array('x')) array('number' => 1, 'values' => array('y')) array('number' => 2, 'values' => array('x','b')) array('number' => 1, 'values' => array('a')) 

Я начал с этого сейчас, но в конце мой мозг горит, и я не знаю, с чего начать сравнивать массивы … Наслаждайтесь!

 $array = array( 'x', 'x', 'y', 'x', 'b', 'x', 'b', 'a' //[.......] [.] [[......] [......]] [.] ); $arrayCount = count($array); $res = array(); for($i = 0; $i < $arrayCount; $i++) { for($j = 1; $j < $arrayCount; $j++) { $res[$i][] = array_slice($array, $i, $j); } } //echo '<pre>'; //var_dump($res); //echo '</pre>'; // //die; $resCount = count($res); $oneResCount = count($res[0]); 

Сначала создайте функцию, которая найдет возможные групповые совпадения в массиве для заданного группового массива, начиная с определенного индекса в массиве и вернет количество найденных совпадений.

 function findGroupMatch($group, $array, $startFrom) { $match = 0; while($group == array_slice($array, $startFrom, count($group))) { $match++; $startFrom += count($group); } return $match; } 

Теперь нам нужно выполнить итерацию по каждому элементу, чтобы найти возможные группы, а затем отправить его в findGroupMatch() чтобы проверить, существует ли какое-либо соответствие для группы в следующих элементах. Трюк для поиска возможной группы – это поиск элемента, который соответствует любому из предыдущих элементов. Если это так, мы найдем возможную группу, берущую все предыдущие элементы, начиная с сопоставленного элемента. В противном случае мы просто увеличиваем список непревзойденных элементов, и в конце мы вводим все непревзойденные элементы как отдельные группы элементов. (В данном примере мы имеем a, b, c, d, a.... Когда мы найдем 2-й a в массиве, он соответствует предыдущему a Итак, рассмотрим a, b, c, d возможную группу и отправьте его в функцию findGroupMatch() , чтобы проверить, сколько еще групп мы найдем в следующих элементах.)

 $array = array( 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'c', 'd', ); $unMatchedItems = array(); $totalCount = count($array); $groupsArray = array(); for($i=0; $i < $totalCount; $i++) { $item = $array[$i]; if(in_array($item, $unMatchedItems)) { $matched_keys = array_keys($unMatchedItems, $item); foreach($matched_keys as $key) { $possibleGroup = array_slice($unMatchedItems, $key); $matches = findGroupMatch($possibleGroup, $array, $i); if ($matches) { //Insert the items before group as single item group if ($key > 0) { for ($j = 0; $j < $key; $j++) { $groupsArray[] = array('number' => 1, 'values' => array($unMatchedItems[$j])); } } //Insert the group array $groupsArray[] = array('number' => $matches + 1, 'values' => $possibleGroup); //number includes initial group also so $matches + 1 $i += (count($possibleGroup) * $matches) - 1; //skip the matched items from next iteration //Empty the unmatched array to start with a new group search $unMatchedItems = array(); break; } } //If there was no matches, add the item to the unMatched group if(!$matches) $unMatchedItems[] = $item; } else { $unMatchedItems[] = $item; } } //Insert the remaining items as single item group for($k=0; $k<count($unMatchedItems); $k++) { $groupsArray[] = array('number' => 1, 'values' => array($unMatchedItems[$k])); } print_r($groupsArray); 

Результат будет таким: (Проверьте этот скрипт PHP для тестирования, а также https://eval.in/507333 для другого теста ввода).

 Array ( [0] => Array ( [number] => 2 [values] => Array ( [0] => a [1] => b [2] => c [3] => d ) ) [1] => Array ( [number] => 1 [values] => Array ( [0] => c ) ) [2] => Array ( [number] => 1 [values] => Array ( [0] => d ) ) ) 

Первый пример суперлегкий с рекурсией. Второй пример … не так-то просто.

Пример ниже работает только для первого примера, если предположить, что ни один шаблон никогда не должен содержать два одинаковых элемента. Это также будет обрабатывать все отдельные шаблоны элементов в конце исходного массива и сохранять порядок шаблонов (первого появления шаблона).

 function find_pattern($input, &$result) { $values = []; // currently processed elements $pattern = ''; // the current element pattern $dupe_found = false; // did we find a duplicate element? // search the values for the first that matches a previous value while ($next = array_shift($input)) { // check if the element was already found if (in_array($next, $values)) { // re-add the value back into the input, since the next call needs it array_unshift($input, $next); // add the resulting pattern add_pattern($pattern, $values, $result); // find the next pattern with a recursive call find_pattern($input, $result); // a duplicate element was found! $dupe_found = true; // the rest of the values are handled by recursion, break the while loop break; } else { // not already found, so store the element and keep going $values[] = $next; // use the element to produce a key for the result set $pattern .= $next; } } // if no duplicate was found, then each value should be an individual pattern if (!$dupe_found) { foreach ($values as $value) { add_pattern($value, [$value], $result); } } } function add_pattern($pattern, $values, &$result) { // increment the pattern count $result[$pattern]['number'] = isset($result[$pattern]['number']) ? result[$pattern]['number']+1 : 1; // add the current pattern to the result, if not already done if (!isset($result[$pattern]['values'])) { $result[$pattern]['values'] = $values; } } 

И пример использования:

 $input = [ 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'c', 'd' ]; $result = []; find_pattern($input, $result); echo "<pre>"; print_r($result); echo "</pre>"; 

Пример вывода:

 Array ( [abcd] => Array ( [number] => 2 [values] => Array ( [0] => a [1] => b [2] => c [3] => d ) ) [c] => Array ( [number] => 1 [values] => Array ( [0] => c ) ) [d] => Array ( [number] => 1 [values] => Array ( [0] => d ) ) ) 

Вы могли бы сделать что-то вроде этого:

 <?php $array = array( 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'c', 'd' ); // Call this function to get your patterns function patternMatching(array $array) { $patterns = array(); $belongsToPattern = array_fill(0, count($array), false); // Find biggest patterns first for ($size = (int) (count($array) / 2); $size > 0; $size--) { // for each pattern: start at every possible point in the array for($start=0; $start <= count($array) - $size; $start++) { $p = findPattern($array, $start, $size); if($p != null) { /* Before we can save the pattern we need to check, if we've found a * pattern that does not collide with patterns we've already found */ $hasConflict = false; foreach($p["positions"] as $idx => $pos) { $PatternConflicts = array_slice($belongsToPattern, $pos, $p["size"]); $hasConflict = $hasConflict || in_array(true, $PatternConflicts); } if(!$hasConflict) { /* Since we have found a pattern, we don't want to find more * patterns for these positions */ foreach($p["positions"] as $idx => $pos) { $replace = array_fill($pos, $p["size"], true); $belongsToPattern = array_replace($belongsToPattern, $replace); } $patterns[] = $p; // or only return number and values: // $patterns[] = [ "number" => $p["number"], "values" => $p["values"]]; } } } } return $patterns; } function findPattern(array $haystack, $patternStart, $patternSize ) { $size = count($haystack); $patternCandidate = array_slice($haystack, $patternStart, $patternSize); $patternCount = 1; $patternPositions = [$patternStart]; for($i = $patternStart + $patternSize; $i <= $size - $patternSize; $i++) { $patternCheck = array_slice($haystack, $i, $patternSize); $diff = array_diff($patternCandidate, $patternCheck); if(empty($diff)) { $patternCount++; $patternPositions[] = $i; } } if($patternCount > 1 || $patternSize <= 1) { return [ "number" => $patternCount, "values" => $patternCandidate, // Additional information needed for filtering, sorting, etc. "positions" => $patternPositions, "size" => $patternSize ]; } else { return null; } } $patterns = patternMatching($array); print "<pre>"; print_r($patterns); print "</pre>"; ?> 

Код может быть далеко не оптимальным по скорости, но он должен делать то, что вы хотите сделать для любой последовательности строк в массиве. patternMatching() возвращает шаблоны, упорядоченные по убыванию в размере шаблона и восходящие по первому вступлению (вы можете использовать ['positions'][0] в качестве критерия сортировки для достижения другого порядка).

Это должно сделать это:

 <?php $array = array( 'x', 'y', 'x', 'y', 'a', 'ab', 'c', 'd', 'a', 'b', 'c', 'd', 'c', 'd', 'x', 'y', 'b', 'x', 'y', 'b', 'c', 'd' ); // convert the array to a string $string = ''; foreach ($array as $a) { $l = strlen($a)-1; $string .= ($l) ? str_replace('::',':',$a[0] . ':' . substr($a,1,$l-1) . ':' . $a[$l]) . '-' : $a . '-'; } // find patterns preg_match_all('/(?=((.+)(?:.*?\2)+))/s', $string, $matches, PREG_SET_ORDER); foreach ($matches as $m) { $temp = str_replace('--','-',$m[2].'-'); $patterns[] = ($temp[0]==='-') ? substr($temp,1) : $temp; } // remove empty values and duplicates $patterns = array_keys(array_flip(array_filter($patterns))); // sort patterns foreach ($patterns as $p) { $sorted[$p] = strlen($p); } arsort($sorted); // find double or more occurences $stringClone = $string; foreach ($sorted as $s=>$n) { $nA = substr_count($stringClone,':'.$s); $nZ = substr_count($stringClone,$s.':'); $number = substr_count($stringClone,$s); $sub = explode('-',substr($stringClone,strpos($stringClone,$s),$n-1)); $values = $sub; if($nA>0 || $nZ>0){ $numberAdjusted = $number - $nA - $nZ; if($numberAdjusted > 1) { $temp = ''; while($n--){ $temp .= '#'; } $position = strpos(str_replace(':'.$s,':'.$temp,str_replace($s.':',$temp.':',$string)),$s); $stringClone = str_replace(':'.$s,':'.$temp,$stringClone); $stringClone = str_replace($s.':',$temp.':',$stringClone); $result['p'.sprintf('%09d', $position)] = array('number'=>$numberAdjusted,'values'=>$values); $stringClone = str_replace($s,'',$stringClone); $stringClone = str_replace($temp,$s,$stringClone); } } else if($number>1){ $position = strpos($string,$s); $result['p'.sprintf('%09d', $position)] = array('number'=>$number,'values'=>$values); $stringClone = str_replace($s,'',$stringClone); } } // add the remaining items $remaining = array_flip(explode('-',substr($stringClone,0,-1))); foreach ($remaining as $r=>$n) { $position = strpos($string,$r); $result['p'.sprintf('%09d', $position)] = array('number'=>1,'values'=>str_replace(':','',$r)); } // sort results ksort($result); $result = array_values($result); print_r($result); ?> 

Рабочий пример здесь .