京东第一题，求相似字符串个数，有大佬ac的吗
京东第一题，求相似字符串，有大佬ac的吗,附60%ac的代码
input:ababcb
xyx
output:3
xyx
output:3
''' input:ababcb xyx output:3 ''' import sys import os import re def KMP(S): m = len(S) N = [0 for i in range(m)] for i in range(1,m): k = N[i-1] while(k>0 and S[i]!=S[k]): k = N[k-1] if(S[i]==S[k]): N[i]=k+1 else: N[i]=0 return N if __name__ == '__main__': S = sys.stdin.readline().strip() T = sys.stdin.readline().strip() len1 = len(S) len2 = len(T) TN = KMP(T) count = 0 if(len1<len2): print(0) sys.exit() for i in range(len1): tmp = S[i:i+len2] tmpN = KMP(tmp) if(len(tmp)<len2): break elif(tmpN==TN): count+=1 print(count)
#京东#
