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?
Optimizing string match algorithm
c++;optimization;strings;programming challenge;time limit exceeded