給定數組中數組元素的最長重複子集

Question

您好我有一個關於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函數？

Answer 1

循環訪問數組，然後在內部循環中搜索所有可能的子串長度。最大重新發生的子字符串最多隻能是陣列長度的一半。

使用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); 

Answer 2

這就是我設法用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; 
} 

Answer 3

In JavaScript做。實際上，你可以有一個最大的，如果你有重疊的字符串重複子比原先的一半長度：字符串「abababababab4」有字符串「ababababab」在索引0和2

// 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.");