java - 这段代码的性能高在哪里了?

Question

代码1:

bool judge(string*strs , int* positions , int n , int k)
{
    string s ;
    for(int i=0 ; i<n  ;i++)
        s+=strs[positions[i]] ;

    string tmp = s ;

    int count = 1 ;

    for(int i=1 ; i<(s.length()/2+1) ; i++)
    {
        tmp = tmp.substr(1) + tmp[0] ;
        if(tmp == s)
        {
             count = s.length()/(i) ;
             break ;
        }
    }

    return count == k ;
}

代码2:

bool judge(string*strs , int* positions , int n , int k)
{
    string str = "" ;
    
    for(int i=0 ; i<n  ;i++)
        str+=strs[positions[i]] ;

    int count = 1 ;
    int length = str.length() ;
    for(int offset=1 ; offset<=(length/2+1) ; offset++)
    {
        int start = 0 ;
        int offStart = offset ;
        bool flag = true ;
        for( ; start<length ; )
        {
            if(str[start] == str[offStart])
            {
                start++ ;
                offStart = (offStart+1)%length ;
            }
            else
            {
                flag = false ;
                break ;
            }
        }

        if(flag)
        {
            count = length/offset ;
            break ;
        }
    }

    return (count == k) ;
}

这两段代码中第一段是我在网上AC一道题的时候参考的, 第二段是我自己写的, 作用是用于比较一个字符串偏移若干位之后是否和原串相同.
第一段就可以ac, 第二段就运行超时了.

我想知道的是第一段代码的性能高在哪里了?

//我主要写的代码是java的, 用java ac不过, 才切C++写...对C++不是很熟练

Answer 1

• 初始化时下面的代码多拷贝了一次，当n较大时，因为差一个常数，差异比较明显；

• 上面的代码使用==进行字符串匹配既string::std::compare方法，编译器会有优化。而下面的代码匹配使用for循环，调用堆栈在n很大时候很耗时间。参考http://stackoverflow.com/ques...

http://stackoverflow.com/ques...