document.write('

如果题目没有对isString使用的限制，那么可以通过求出s2进行旋转的所有组合，然后与s1进行比较。但是这种方法的时间复杂度比较高。通过对字符

串旋转进行仔细分析，发现对字符串s1进行旋转得到的字符串一定是s1s1的子串。因此可以通过判断s2是否是s1s1的子串来判断s2能否通过旋转s1得

到。例如：s1=“waterbottle”，那么s1s1=“waterbottlewaterbottle”，显然s2是s1s1的子串，因此s2能通过旋转s1得到。实现代码如下：

#函数功能:判断str2是否为str1的子串

def isSubstring(str1,str2):

return str1.find(str2)!=-1

#函数功能: 判断str2是否可以通过旋转str1得到

def rotateSame(str1,str2):

if str1==None or str2==None:

return False

len1=len(str1)

len2=len(str2)

#判断两个字符串长度是否相等, 如果不相等, 那么不可能通过旋转得到

if len1!=len2:

return False

#申请临时空间存储str1str1, 多申请了一个空间存储\'\\0\'

tmp=[None]*(2*len1+1)

#是tmp为str1str1

i=0

while i＜len1:

tmp[i]=list(str1)[i]

tmp[i+len1]=list(str1)[i]

i+=1

tmp[2*len1]=\'\\0\'

#判断str2是否为tmp的子串

result=isSubstring(".join(tmp),str2)

return result

if __name__=="__main__":

str1="waterbottle"

str2="erbottlewat"

result=rotateSame(str1,str2)

if result:

print str2+"可以通过旋转"+str1+\'得到"

else:

print str2+"不可以通过旋转"+str1+"得到"

程序的运行结果为：

erbottlewat可以通过旋转waterbottle得到

为了简单起见，这种方法中isSubstring通过调用库函数的方式进行了实现，当然在采用KMP算法实现的isSubstring的效率最高。

算法性能分析：

这种方法首先对字符串str1进行了一次遍历，时间复杂度为O(N)(其中，N为字符串的长度)，接着调用了isSubstring函数(假设采用了KMP算法)，这种方法的时间复杂度为O(2N+N)=O(3N)，因此，整个算法的时间复杂度为O(N)。此外这种方法申请了2N+1个存储空间，因此，算法的空间复杂度也为O(N)。

');