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. sstring 内でが最初に出現する場所を検索します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 のままである Sunday Search を使用して、独自の部分文字列の一致も試しました。

2. 私は学生ではないので、宿題の手伝いは求めていません。私は働く専門家です。ACM の問題を解決することは、私の趣味です。

助けてください。