javascript - 给定数组中数组元素的最长重复子集

Question

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

示例:

my_array['b','r','o','w','n','f','o','x','h','u','n ',','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);