2

嗨，我有一个关于 jquery 的问题，我需要从给定数组中找到最长的重复子集。

例子：

my_array['b','r','o','w','n','f','o','x','h','u','n','t','e','r','n','f','o','x','r','y','h','u','n']

结果应该是 nfox。我有以下代码：

 string = my_array.join('');
 for(i=0; i < my_array.length; i++)
 {

  for(j=0; j < my_array.length; j++)
 {

 string.substring(Math.abs(j-i));
 }

 }

但它似乎不像我想要的那样工作，也许我错过了一些 jquery 功能？

4

4 回答 4

3

遍历数组，然后在内部循环中搜索所有可能的子字符串长度。最大重复出现的子字符串最多只能是数组长度的一半。

使用indexOf和indexLastOf函数来搜索重新出现的子字符串。如果两个函数都找到子字符串并且找到的位置不同，则子字符串重新出现。

my_array = ['b','r','o','w','n','f','o','x','h','u','n','t','e','r','n','f','o','x','r','y','h','u','n'];
    str = my_array.join('');

    var greatestLen = 0;
    var highestPosn1 = -1;
    var highestPosn2 = -1;

    for (var n = 0; n < my_array.length; ++n)
    {
        for (var l = 1; l <= my_array.length/2; ++l)
        {
            var subs = str.substr(n,l);
            var find1 = str.indexOf(subs);
            var find2 = str.lastIndexOf(subs);
            if (find1 != -1 && find2 != -1 && find1 != find2)
            {
                var longestSubString = subs;
                if (longestSubString.length > greatestLen)
                {
                    highestPosn1 = find1;
                    highestPosn2 = find2;
                    greatestLen = longestSubString.length;
                }
            }
        }
    }
    console.info('Longest substr ' + greatestLen + ' at posn1=' + highestPosn1 + ' and posn2=' + highestPosn2);
于 2013-07-27T10:22:01.797 回答
0

在 JavaScript中。如果您包含重叠字符串，您实际上可以拥有超过原始长度一半的最大重复子字符串：字符串“abababababab4”在索引 0 和 2 处具有字符串“ababababab”

// For some fancy printing
function post(string) {
    document.getElementById("stati").innerHTML += string;
}

var myarray = ['b','r','o','w','n',
               'f','o','x',
               'h','u','n','t','e','r',
               'n','f','o','x',
               'r','y','h','u','n'];
var string = myarray.join("");
var longestRepeated = "";

// i = current size of substring
// i loop runs string.length times;
// looks for large repeated substrings first
for (i = string.length; i > 0; i--) {
    post("<code>Searching all substrings of length " + i + "</code><br>");

    // j = current beginning index of substring
    // j loop runs (string.length - substring.length + 1) times;
    // checks for repeat of subStr in
    // range (indexOf(subStr), whileCurrentSizeiStillFitsInString]
    for (j = 0; j < string.length - i; j++) {
        var subStr = string.substring(j, j + i);
        post("<code class='a'>at index " + j + ", substring = '" +
              subStr + "'</code><br>");

        // if subStr is matched between indexOf(subStr) + 1 and
        // the end of the string, we're done here
        // (I'm not checking for multiple repeated substrings
        //  of the same length. Get over it.)
        if (string.indexOf(subStr, j + 1) != -1) {
            longestRepeated = subStr;
            break;
        }
    }
    if (longestRepeated.length) break;
}

if (longestRepeated.length) alert("Longest repeated substring: " +
                                   subStr);
else alert("Longest repeated substring is the whole string.");
于 2013-07-27T11:17:10.043 回答
0

这就是我设法用 php 做的事情

function longest_subset ($input = array()) {
$longestSubstring = "";
$inputString =implode("",$input);
echo $inputString;
if (!is_array($input)) {
throw new InvalidArgumentException("Invalid Input Type", 1);
}
if (empty($input)) {
throw new LengthException("Your array must contain one or more values", 1);
}

for( $i=0; $i < strlen($inputString); $i++) {
for( $j=0; $j < strlen($inputString); $j++) {
$length = abs($j-$i);
echo $length.'<br>';

$substring = substr($inputString, $i, $length);
//echo $substring.'<br>';

$doesSubstringRepeat = strrpos($inputString,$substring) > $i;
$substringLongerThanLongest = strlen($substring) > strlen($longestSubstring);

if ($doesSubstringRepeat && $substringLongerThanLongest) {
$longestSubstring = $substring;
}
}
}

return strlen($longestSubstring) > 0 ? str_split($longestSubstring) : false;
}
于 2013-07-27T10:59:59.267 回答
0

如果有人仍然需要这个，这里有一个更通用的解决方案，它不关心数组内容并返回最长的重复子集，同时考虑到元素的类型。

function solve(array $list): array
{
    $length = count($list);
    $longestRepeatedSequenceLength = intdiv($length + 1, 2);

    while ($longestRepeatedSequenceLength > 0) {
        $possibleIterations = intdiv($length, $longestRepeatedSequenceLength);

        for ($i = 0; $i < $possibleIterations; $i++) {
            $offset = $longestRepeatedSequenceLength + $i;

            if ($length - $offset < 0) {
                continue;
            }

            $subset = array_slice($list, $i, $longestRepeatedSequenceLength);

            // take overlapping strings in consideration
            $testIn = ($longestRepeatedSequenceLength > 1) ?
                array_slice($list, $offset - 1, $length - $offset + 1) :
                array_slice($list, $offset, $length - $offset);

            if (isSubset($testIn, $subset)) {
                return $subset;
            }
        }

        $longestRepeatedSequenceLength--;
    }

    return [];
}

此解决方案考虑了重叠的子集，您可以对其进行编辑，以便仅通过以下行替换速记 if 语句（在注释下）来不考虑它们：

$testIn = array_slice($list, $offset, $length - $offset);

干得好：

function isSubset(array $arr, array $subArray): bool
{
    if (count($arr) < count($subArray)) {
        return false;
    }

    $keys = array_keys($arr, $subArray[array_keys($subArray)[0]]);

    foreach ($keys as $k) {
        if (array_slice($arr, $k, count($subArray)) === $subArray) {
            return true;
        }
    }

    return false;
}
于 2019-09-28T09:56:39.537 回答