7
\$\begingroup\$

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?

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ thanks ewert. that's exactly what i am looking for... :) now i have to just study this topic. \$\endgroup\$ – Nishchay Sharma Dec 12 '11 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.