title: Algorithm for finding all of the shared substrings of any length between 2 strings, and then counting occurrences in string 2?
body: <p>I've run into an unusual challenge and so far I'm unable to determine the most efficient algorithm to attack this.</p>
  
  <hr>
  
  <p><strong>Given the following 2 strings as an example, find all commonly shared substrings between the 2 strings of any length, and count the number of occurrences of all of those shared substrings in string 2. Your algorithm also needs to be able to compute shared substrings between files containing strings that are up to 100MB or more in size.</strong></p>
  
  <p>Example:</p>
  
  <p>String 1: ABCDE512ABC361EG51D</p>
  
  <p>String 2: ADE5AHDW4131EG1DG5C</p>
  
  <p>Given these 2 strings this algorithm would find the following shared substrings:
  A,C,D,E,5,1,3,G,DE,E5,EG,G5,1D,DE5,1EG</p>
  
  <p>And then from these commonly shared substrings, we'd find how many occurences there are of each of them in string 2. </p>
  
  <p>A: 2 occurrences in string 2</p>
  
  <p>C: 1 occurence in string 2</p>
  
  <p>D: 3 occurrences in string 2</p>
  
  <p>etc..</p>
  
  <hr>
  
  <p>The first approach I took to wrap my head around this problem was brute forcing my way through computing the common shared substrings using 2 nested for loops - obviously the least efficient but it was a quick and dirty way to get an idea of what the expected outputs should be with smaller test input and the slowest possible time to run, which was around 2 minutes to compute all common shared substrings between 2 files containing ascii strings with a size of 50kb. Upping the size to 1mb made this come to a screeching halt due to the massive number of total nested iterations that had to occur to compute this.</p>
  
  <p>The next approach was using trees - seeing how much memory I could trade off to optimize compute time. This approach was much faster. The same two 50kb files that took 2 minute with the brute force method were near instant. Running against 1mb files was very fast too still (seconds) but as I continued to test with larger and larger file sizes, I quickly began running into memory issues due to tree sizes.</p>
  
  <hr>
  
  <p>Note: The string files will only ever contain ASCII characters!</p>
  
  <hr>
  
  <p><strong>Edit:</strong> </p>
  
  <p><strong><em>I'm escalating this a bit further, please see:</em></strong></p>
  
  <p><a href="https://gist.github.com/braydo25/f7a9ce7ce7ad7c5fb11ec511887789bc" rel="nofollow noreferrer">https://gist.github.com/braydo25/f7a9ce7ce7ad7c5fb11ec511887789bc</a></p>