Brett DeWoody Brett DeWoody - 4 months ago 15
Javascript Question

Find all strings of length 1 through N in String of length N

I'm trying to find all substrings within an string. That is, all strings of length 1 through N in a string of length N.

Example

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


First Attempt

I have a solution that works on strings of relatively small N but on larger Ns the solution is extremely slow. Here's the current solution:

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


How can I improve the performance of the algorithm to return all substrings?

Answer

As other commenters have noted, there is not much to improve here. Here's probably the best possible javascript version, with two optimizations applied:

  1. Changed slice to growing strings instead.

  2. Changed while loop to for loop. For some reason this made it 100ms faster. (It seems the increase in speed was because of an error in code, thanks @le_m for noticing)

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;