class Solution:
def getNext(self,next,s):
j=0
next[0]=0
for i in range(1,len(next)):
while j>0 and s[i]!=s[j]:
j=next[j-1]
if s[i]==s[j]:
j+=1
next[i]=j
def strStr(self, haystack: str, needle: str) -> int:
next=[0]*len(needle)
self.getNext(next,needle)
j=0
for i in range(len(haystack)):
while j>0 and haystack[i]!=needle[j]:
j=next[j-1]
if haystack[i]==needle[j]:
j+=1
if j==len(needle):
return i-len(needle)+1
return -1
好难
class Solution:
def getNext(self,next,s):
j=0
next[0]=0
for i in range(1,len(next)):
while j>0 and s[i]!=s[j]:
j=next[j-1]
if s[i]==s[j]:
j+=1
next[i]=j
def repeatedSubstringPattern(self, s: str) -> bool:
j=0
next=[0]*len(s)
self.getNext(next,s)
if next[-1]!=0 and len(s)%(len(s)-next[-1])==0:
return True
return False