javascript - 最长重复子串函数的错误结果

Question

我正在编写一个 JavaScript 函数，用于查找长字符串中的重复短语。该字符串将使用 Unicode 和非英语，这使我无法使用 RegExp。在这个 99 瓶啤酒的例子中，结果应该是“墙上的啤酒瓶”，“取下一瓶，传来传去”等没有数字，只有重复出现的部分，但它给出了错误的结果:

window.findRepeats=function(){
 inputString=document.getElementById("txt1").value;
 
 outputArray=[];
 for(originalStart=0;originalStart<inputString.length;originalStart++){
  for(copyStart=originalStart+1;copyStart<inputString.length;copyStart++){
   if(inputString[originalStart]==inputString[copyStart]){
    for(windowByte=originalStart+1;windowByte<copyStart;windowByte++){
     if(inputString[windowByte]!=inputString[copyStart-originalStart+windowByte]){
      break;
      }
     if(windowByte>originalStart+1){
      outputArray.push([originalStart,windowByte]);
      }
     }
    }
   }
  }
 for(arrayCounter=0;arrayCounter<outputArray.length;arrayCounter++){
  outputArray[arrayCounter]+=":"+inputString.substring(outputArray[arrayCounter][0],outputArray[arrayCounter][1]);
  }
 document.getElementById("txt2").value=outputArray.join("\n");
 }

<textarea rows=9 id="txt1">
99 bottles of beer on the wall, 99 bottles of beer.
Take one down and pass it around, 98 bottles of beer on the wall.
98 bottles of beer on the wall, 98 bottles of beer.
Take one down and pass it around, 97 bottles of beer on the wall.
97 bottles of beer on the wall, 97 bottles of beer.
Take one down and pass it around, 96 bottles of beer on the wall.
96 bottles of beer on the wall, 96 bottles of beer.
Take one down and pass it around, 95 bottles of beer on the wall.
95 bottles of beer on the wall, 95 bottles of beer.
Take one down and pass it around, 94 bottles of beer on the wall.


</textarea>
<br>
    
<textarea rows=9 id="txt2">
    
</textarea>
<br>
<input type="button" value="go" onclick='findRepeats()'>
    
</input>

如果您查看结果，它会给出所有重复的子串，但不会给出最长的子串。我只想要最长的子串。至于后缀数组和树，我至今没能理解这些，所以我不得不处理这种方法。

Answer 1

SOSO 工作

这个怎么样？

显然，您的原始函数有错误，结果有些不对。我现在将尝试简化代码。

window.findRepeats=function(){
  var inputString = document.getElementById("txt1").value;
  var outputArray=[];
  for(originalStart=0;originalStart<inputString.length;originalStart++){
    for(copyStart=originalStart+1;copyStart<inputString.length;copyStart++){
      if(inputString[originalStart]==inputString[copyStart]){
        for(windowByte=originalStart+1;windowByte<copyStart;windowByte++){
          if(inputString[windowByte]!=inputString[copyStart-originalStart+windowByte]){
            break;
          }
          if(windowByte>originalStart+1){
            outputArray.push([originalStart,windowByte+1]);
          }
        }
      }
    }
  }
  var shorts = [];
  for(var i=0;i<outputArray.length;i++){
    var curString = inputString.substring(outputArray[i][0],outputArray[i][1]);
    if (curString[0] === " ")
      curString = curString.substr(1);
    if (curString.trim() != "")
      shorts.push(curString);
  }
  var uniq = removeDuplicate(shorts);
  for (var j=uniq.length-1;j>-1;j--){
    for (var k=uniq.length-1;k>-1;k--){
      if (uniq[j].indexOf(uniq[k]) > -1) {
        uniq[k]=uniq[j];
      }
    }
  }
  uniq = removeDuplicate(uniq);
  shorts = uniq;
  document.getElementById("txt2").value=shorts.join("\n----------------\n");
}
function removeDuplicate(arr) {
  return arr.slice().sort(function(a,b){return a > b}).reduce(function(a,b){if (a.slice(-1)[0] !== b) a.push(b);return a;},[]);
}

<textarea rows=9 style="width:100%" id="txt1">3 bottles of beer on the wall, 3 bottles of beer.
Take one down and pass it around, 2 bottles of beer on the wall.

2 bottles of beer on the wall, 2 bottles of beer.
Take one down and pass it around, 1 bottle of beer on the wall.

1 bottle of beer on the wall, 1 bottle of beer.
Take one down and pass it around, no more bottles of beer on the wall.

No more bottles of beer on the wall, no more bottles of beer.
Go to the store and buy some more, 99 bottles of beer on the wall.</textarea>
<br>
    
<textarea rows=9 style="width:100%" id="txt2"></textarea>
<br>
<input type="button" value="go" onclick='findRepeats()'>