Can you speed up this algorithm? C# / C++ : <p>Hey I've been working on something from time to time and it has become relatively large now (and slow). However I managed to pinpoint the bottleneck after close up measuring of performance in function of time.</p>

<p>Say I want to "permute" the string "ABC". What I mean by "permute" is not quite a permutation but rather a continuous substring set following this pattern:</p>

<pre><code>A
AB
ABC

B
BC

C
</code></pre>

<p>I have to check for every substring if it is contained within another string S2 so I've done some quick'n dirty literal implementation as follows:</p>

<pre><code>for (int i = 0; i &lt;= strlen1; i++)
{
   for (int j = 0; j &lt;= strlen2- i; j++)
   {
      sub = str1.Substring(i, j);
      if (str2.Contains(sub)) {do stuff}
      else break;
</code></pre>

<p>This was very slow initially but once I realised that if the first part doesnt exist, there is no need to check for the subsequent ones meaning that if sub isn't contained within str2, i can call break on the inner loop.</p>

<p>Ok this gave blazing fast results but calculating my algorithm complexity I realised that in worst case this will be N^4 ? I forgot that str.contains() and str.substr() both have their own complexities (N or N^2 I forgot which).</p>

<p>The fact that I have a huge amount of calls on those inside a 2nd for loop makes it perform rather.. well N^4 ~ said enough.</p>

<p>However I calculated the average run-time of this both mathematically using probability theory to evaluate the probability of growth of the substring in a pool of randomly generated strings (this was my base line) measuring when the probability became > 0.5 (50%)</p>

<p>This showed an exponential relationship between the number of different characters and the string length (roughly) which means that in the scenarios I use my algorithm the length of string1 wont (most probably) never exceed 7</p>

<p>Thus the average complexity would be ~O(N * M) where N is string length1 and M is string length 2. Due to the fact that I've tested N in function of constant M, I've gotten linear growth ~O(N) (not bad opposing to the N^4 eh?)</p>

<p>I did time testing and plotted a graph which showed nearly perfect linear growth so I got my actual results matching my mathematical predictions (yay!)</p>

<p>However, this was NOT taking into account the cost of string.contains() and string.substring() which made me wonder if this could be optimized even further?</p>

<p>I've been also thinking of making this in C++ because I need rather low-level stuff? What do you guys think? I have put a great time into analysing this hope I've elaborated everything clear enough :)!</p>
