주어진 배열 배열 요소의 가장 긴 반복 된 하위 집합

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는"문자열 인덱스 0에서 "ababababab"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.");