title: Longest Repeated Substring Better Complexity
body: <p>I have implemented a solution by comparing the suffixes of a string after sorting the suffix list. Is there any linear time algorithm that performs better than this piece of code?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;cstring&gt;
  #include &lt;algorithm&gt;
  using namespace std;
  void preCompute(string input[],string s)
  {
      int n = s.length();
      for(int i=0; i&lt;n; i++)
          input[i] = s.substr(i,n);
  }
  string LongestCommonSubString(string first,string second)
  {
      int n = min(first.length(),second.length());
      for(int i=0; i&lt;n; i++)
          if(first[i]!=second[i])
              return first.substr(0,i);
      return first.substr(0,n);
  }
  string lrs(string s)
  {
      int n = s.length();
      string input[n];
      preCompute(input,s);
      sort(input, input+n);
      string lrs = "";
      for(int i=0; i&lt;n-1; i++)
      {
          string x = LongestCommonSubString(input[i],input[i+1]);
          if(x.length()&gt;lrs.length())
          {
              lrs = x;
          }
      }
      return lrs;
  }
  int main()
  {
      string input[2] = {"banana","missisipi"};
      for(int i=0;i&lt;2;i++)
          cout&lt;&lt;lrs(input[i])&lt;&lt;endl;
      return 0;
  }
  </code></pre>
  
  <p>I found a really good resource for this question. See <a href="http://www.cs.iastate.edu/~cs548/references/linear_lcp.pdf" rel="nofollow">here</a></p>