Optimizing string match algorithm

Question

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 <iostream>
#include <cstring>

using namespace std;

int n;
char str[1000000];

int sim(int i, int len)
{
    int j=0;
    for(; i<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<len; i++)
    {
        count+=sim(i, len);
    }
    cout<<count<<endl;
}

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>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?

Answer 1

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 < and << and +=