Optimizing string match algorithm I was trying to solve this problem.  I thought of any possible relation between the number of matches among subsequent substrings, but could not find one. So, the probably naive solution that I drafted was:

#include &lt;iostream&gt;
#include &lt;cstring&gt;

using namespace std;

int n;
char str[1000000];

int sim(int i, int len)
{
    int j=0;
    for(; i&lt;len; i++, j++)
    {
        if(str[i]!=str[j])
            return j;
    }
    return j;
}

void solve()
{
    int len=strlen(str);
    int count=len;

    for(int i=1; i&lt;len; i++)
    {
        count+=sim(i, len);
    }
    cout&lt;&lt;count&lt;&lt;endl;
}

int main()
{
    cin&gt;&gt;n;
    for(int i=0; i&lt;n; i++)
    {
        cin&gt;&gt;str;
        solve();
    }

    return 0;
}


Now submission to online judge at interviewstreet says that I did pass 7/10 testcases but the time limit exceeded for the 8th testcase! It means that my solution isn't even that naive, but it also indicates a need for some optimization. Can you people please suggest any way to optimize it?
I think what you need is a suffix tree: http://en.wikipedia.org/wiki/Suffix_tree. I don't really remember much about it, except that it exists and seems relevant to the problem at hand.

Style wise, I recommend spaces around operators like &lt; and &lt;&lt; and +=