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?
