Brett DeWoody - 1 year ago 68
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?

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;``````

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download