CODEWITHSUNDEEP
c++stringalgorithm
Peter Lee
Peter Lee

Reputation: 13839

Can It Be Faster to Find the Minimum Periodic String Inside Another String in Terms of Time Complexity

I'm trying to solve this ACM problem (10298 - Power Strings): http://uva.onlinejudge.org/external/102/10298.html

The problem is to find the minimum periodic string inside of another string. For example:

Test Input:

abcd
aaaa
ababab

Test Output:

1
4
3

My idea is:

  1. Let s be the input string;
  2. Make a string ss from s+s, and shift the first character;
  3. Find the first occurrence of s in string ss.

Below is my code:

inline int GetLargestN(const char* cs)
{
    string s(cs);
    string ss(s, 1); ss += s; ss += s[0];

    int len = s.length();
    int pos = ss.find(s);

    return len/(pos+1);
}

http://www.cplusplus.com/reference/string/string/find/ string::find should be O(n)

However, I keep getting Time Limitation Exceeds

NOTES:

  1. I also tried my own find substring match using Sunday Search, whose time complexity is also O(n), but still TLE.

  2. I am NOT a student, so I am NOT asking for home assignment help. I'm a working professional. Solving ACM problems is just my hobby.

Please help.

Upvotes: 1

Views: 2867

Answers (1)

Peter Lee
Peter Lee

Reputation: 13839

OK. I switched to use the native C function strstr, and it got accepted, which does NOT make too much sense!

/* Memory allocated in the main function, M is too big, we have to allocate in the heap */
char* s  = new char[M];
char* ss = new char[M*2];

int GetLargestN(const char* s, char* ss)
{
    int n = strlen(s);

    strcpy(ss, s+1); strcpy(ss+n-1, s); ss[n*2] = s[0]; ss[n*2+1] = 0;

    int p = strstr(ss, s)-ss;

    return n/(p+1);
}

Here was the submission:

#       Problem     Verdict     Language    Run Time    Submission Date
12538969    10298   Power Strings   Accepted    C++     0.135   2013-10-22 03:48:14
12534976    10298   Power Strings   Time limit exceeded     C++     3.000   2013-10-21 07:42:46
12534959    10298   Power Strings   Time limit exceeded     C++     3.000   2013-10-21 07:37:16
12534922    10298   Power Strings   Time limit exceeded     C++     3.000   2013-10-21 07:26:16
12534863    10298   Power Strings   Time limit exceeded     C++     3.000   2013-10-21 07:04:21

Upvotes: 3

Related Questions