循环旋转字符串判定：O(n)解法为何被判O(n²)超时？

在Coding Ninjas平台遇到一道题目：判断一个字符串能否通过向右循环旋转得到另一个字符串。我的解法思路是将原字符串拼接自身，再调用find函数检查目标字符串是否存在于拼接后的字符串中。我认为find函数的时间复杂度为O(n)，但提交后出现超时（TLE），平台判定该代码时间复杂度为O(n²)，想请教这一情况的原因。我的代码如下：

int isCyclicRotation(string &p, string &q) 
{
    if(q.size()!=p.size()){
        return 0;
    }
    string s=p+p;
    int sz=s.size();
    int qz=q.size();
    if(s.find(q)!=string::npos){
        return 1;
    }
    return 0;
}

你的核心思路是正确的：若q是p的循环旋转，那q一定是p+p的子串，但问题出在C++标准库string::find的实现细节上：

• C++标准并没有强制要求find使用线性时间的字符串匹配算法（比如KMP、Boyer-Moore），多数编译器的默认实现采用的是朴素字符串匹配算法。
• 朴素算法在最坏场景下的时间复杂度为O(n*m)，这里拼接后的字符串长度是2n，目标字符串长度是n，整体时间复杂度就会达到O(n²)，当测试用例的字符串长度很大时，就会触发超时。

要解决这个问题，你可以自己实现线性时间复杂度的字符串匹配算法（比如KMP）来替代string::find，这样就能把整体时间复杂度降到O(n)，避免超时。

内容的提问来源于stack exchange，提问作者Sleepy Tinker