javascript - 在长度为 N 的字符串中查找所有长度为 1 到 N 的字符串

Question

我正在尝试查找一个字符串中的所有子字符串。即，长度为 N 的字符串中长度为 1 到 N 的所有字符串。

示例

N = '1079'
subStrings = [1,0,7,9,10,07,79,107,079,1079]

第一次尝试

我有一个解决方案适用于相对较小的 N 的字符串，但在较大的 N 上，该解决方案非常慢。这是当前的解决方案:

N = 'somestring'
l = N.length
k = 1
subStrings = []

while (k <= l) {
  i = 0
  while (i + k <= l) {
    subStrings.push(N.slice(i,k+i))
    i++
  } 
  k++
}

// subStrings is an array containing the substrings

如何提高算法的性能以返回所有子字符串？

Answer 1

正如其他评论者所指出的，这里没有太多需要改进的地方。这可能是最好的 javascript 版本，应用了两个优化:

1. 将 slice 改为增长字符串。

注意:这似乎只对长序列数字和小集合有帮助。经过足够多的迭代后，V8 对 noslice 进行了足够的预热优化，使其变得比这种“增长字符串”方法更快。有关此现象的讨论，请参阅评论。

1. 将 while 循环更改为 for 循环。出于某种原因，这使它快了 100 毫秒。(速度的提高似乎是因为代码中的错误，感谢@le_m 的注意)

var start = new Date().getTime();

N = '23692719352345230452034523045823751925012830428043850348503834702834028305724087283409823058402897345982735402934579823750982734590123457239845723972345897234958732495872384957239846752397459327459238645972634598236452389457629346592387465923108457429386419659217834595873459872349576239487523947859872593487529384577823419823641829375412938742119482739107423481290734981236591206752871439071452398457213864957613593184721398471329874129083471293874219356129375421304712938743467812938461239561239874673291847129836451923865449825129873432874192837549281735892317432098491273498123675491238412635496213421394752369271935234523045203452304582375192501283042804385034850383470283402830572408728340982305840289734598273540293457982375098273459012345723984572397234589723495873249587238495723984675239745932745923864597263459823645238945762934659238746592310845742938641965921783459587345987234957623948752394785987259348752938457782341982364182937541293874211948273910742348129073498123659120675287143907145239845721386495761359318472139847132987412908347129387421935612937542130471293874346781293846123956123987467329184712983645192386544982512987343287419283754928173589231743209849127349812367549123841263549621342139475236927193523452304520345230458237519250128304280438503485038347028340283057240872834098230584028973459827354029345798237509827345901234572398457239723458972349587324958723849572398467523974593274592386459726345982364523894576293465923874659231084574293864196592178345958734598723495762394875239478598725934875293845778234198236418293754129387421194827391074234812907349812365912067528714390714523984572138649576135931847213984713298741290834712938742193561293754213047129387434678129384612395612398746732918471298364519238654498251298734328741928375492817358923174320984912734981236754912384126354962134213947523692719352345230452034523045823751925012830428043850348503834702834028305724087283409823058402897345982735402934579823750982734590123457239845723972345897234958732495872384957239846752397459327459238645972634598236452389457629346592387465923341084574293864196592178345958734598723495762394875239478598725934875293845778234198236418293754129387421194827391074234812907349812365912067528714390714523984572138649576135931847213984713298741290834712938742193561293754213047129387434678129384612395612398746732918471298364519238654498251298734328741928375492817358923174320984912734981236754912384126354962133243242139475';

l = N.length;
k = 1;
subInts = [];

for (i = 0; i < l; i++) {
  num = "";
  for (k = 1; k < l-i+1; k++) {
    num += N.charAt(i+k-1);
    subInts.push(num);
  }
} 

var end = new Date().getTime();
var time = end - start;
document.body.textContent = 'Execution time: ' + time + '; Elements: ' + subInts.length;