<p>Suffix arrays are the right idea, but there's a non-trivial piece missing, namely, identifying what are known in the literature as "supermaximal repeats". Here's a GitHub repo with working code: <a href="https://github.com/eisenstatdavid/commonsub" rel="nofollow noreferrer">https://github.com/eisenstatdavid/commonsub</a> . Suffix array construction uses the SAIS library, vendored in as a submodule. The supermaximal repeats are found using a corrected version of the pseudocode from <code>findsmaxr</code> in <a href="https://arxiv.org/pdf/1304.0528.pdf" rel="nofollow noreferrer">Efficient repeat finding via suffix arrays
(Becher&ndash;Deymonnaz&ndash;Heiber)</a>.</p>

<pre><code>static void FindRepeatedStrings(void) {
  // findsmaxr from https://arxiv.org/pdf/1304.0528.pdf
  printf("[");
  bool needComma = false;
  int up = -1;
  for (int i = 1; i &lt; Len; i++) {
    if (LongCommPre[i - 1] &lt; LongCommPre[i]) {
      up = i;
      continue;
    }
    if (LongCommPre[i - 1] == LongCommPre[i] || up &lt; 0) continue;
    for (int k = up - 1; k &lt; i; k++) {
      if (SufArr[k] == 0) continue;
      unsigned char c = Buf[SufArr[k] - 1];
      if (Set[c] == i) goto skip;
      Set[c] = i;
    }
    if (needComma) {
      printf("\n,");
    }
    printf("\"");
    for (int j = 0; j &lt; LongCommPre[up]; j++) {
      unsigned char c = Buf[SufArr[up] + j];
      if (iscntrl(c)) {
        printf("\\u%.4x", c);
      } else if (c == '\"' || c == '\\') {
        printf("\\%c", c);
      } else {
        printf("%c", c);
      }
    }
    printf("\"");
    needComma = true;
  skip:
    up = -1;
  }
  printf("\n]\n");
}
</code></pre>

<p>Here's a sample output on the text of the first paragraph:</p>

<pre><code>Davids-MBP:commonsub eisen$ ./repsub input
["\u000a"
," S"
," as "
," co"
," ide"
," in "
," li"
," n"
," p"
," the "
," us"
," ve"
," w"
,"\""
,"&amp;ndash;"
,"("
,")"
,". "
,"0"
,"He"
,"Suffix array"
,"`"
,"a su"
,"at "
,"code"
,"com"
,"ct"
,"do"
,"e f"
,"ec"
,"ed "
,"ei"
,"ent"
,"ere's a "
,"find"
,"her"
,"https://"
,"ib"
,"ie"
,"ing "
,"ion "
,"is"
,"ith"
,"iv"
,"k"
,"mon"
,"na"
,"no"
,"nst"
,"ons"
,"or"
,"pdf"
,"ri"
,"s are "
,"se"
,"sing"
,"sub"
,"supermaximal repeats"
,"te"
,"ti"
,"tr"
,"ub "
,"uffix arrays"
,"via"
,"y, "
]
</code></pre>
Most efficient way to search for unknown patterns in a string?
<p>I am trying to find patterns that:</p>

<ul>
<li>occur more than once</li>
<li>are more than 1 character long</li>
<li>are not substrings of any other known pattern</li>
</ul>

<p>without knowing any of the patterns that might occur.</p>

<p>For example:</p>

<ul>
<li>The string "the boy fell by the bell" would return <code>'ell', 'the b', 'y '</code>.</li>
<li>The string "the boy fell by the bell, the boy fell by the bell" would return <code>'the boy fell by the bell'</code>.</li>
</ul>

<p>Using double for-loops, it can be brute forced <strong><em>very</em></strong> inefficiently:</p>

<pre><code>ArrayList&lt;String&gt; patternsList = new ArrayList&lt;&gt;();
int length = string.length();
for (int i = 0; i &lt; length; i++) {
    int limit = (length - i) / 2;
    for (int j = limit; j &gt;= 1; j--) {
        int candidateEndIndex = i + j;
        String candidate = string.substring(i, candidateEndIndex);

        if(candidate.length() &lt;= 1) {
            continue;
        }

        if (string.substring(candidateEndIndex).contains(candidate)) {
            boolean notASubpattern = true;
            for (String pattern : patternsList) {
                if (pattern.contains(candidate)) {
                    notASubpattern = false;
                    break;
                }
            }

            if (notASubpattern) {
                patternsList.add(candidate);
            }
        }
    }
}
</code></pre>

<p>However, this is incredibly slow when searching large strings with tons of patterns.</p>