c++ - 在时间复杂度方面是否可以更快地找到另一个字符串中的最小周期字符串

Question

我正在尝试解决这个 ACM 问题（10298 - Power Strings）：http ://uva.onlinejudge.org/external/102/10298.html

问题是在另一个字符串中找到最小周期字符串。例如：

测试输入：

abcd
aaaa
ababab

测试输出：

1
4
3

我的想法是：

1. 设s为输入字符串；
2. ss从中创建一个字符串s+s，并移动第一个字符；
3. s在 string 中查找第一次出现的ss。

下面是我的代码：

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 应该是 O(n)

但是，我不断收到超过时间限制

笔记：

1. 我还使用周日搜索尝试了自己的find子字符串匹配，其时间复杂度也是 O(n)，但仍然是 TLE。

2. 我不是学生，所以我不要求家庭作业帮助。我是一个工作的专业人士。解决 ACM 问题只是我的爱好。

请帮忙。

Answer 1

好的。我改用原生 C 函数 strstr，它被接受了，这没有太大意义！

/* 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);
}

这是提交的内容：

#       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