京东第一题，求相似字符串个数，有大佬ac的吗

京东第一题，求相似字符串，有大佬ac的吗,附60%ac的代码

input:ababcb
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)

#京东#

全部评论

推荐最新楼层

福厂福报福气来

北京邮电大学算法工程师

a了75%，哎

点赞回复分享

发布于 2018-09-09 21:14

Raywall

中国科学技术大学算法工程师

只过了83.。。。

点赞回复分享

发布于 2018-09-09 21:15

机灵的候选人在参加牛客活动

华南理工大学算法工程师

爆破75%，没法了

点赞回复分享

发布于 2018-09-09 21:18

都是好事儿

北京邮电大学 Java

mark，坐等ac代码

点赞回复分享

发布于 2018-09-09 21:19

Debug201711141458424

西安邮电大学算法工程师

点赞回复分享

发布于 2018-09-09 21:20

streamer

北京工业大学算法工程师

def Similar(s,t,n): flag=True dic={} for i in range(n): if s[i] in dic.keys(): if dic[s[i]]==t[i]: continue else: flag=False break elif t[i] in dic.values(): flag=False break else: dic[s[i]]=t[i] return flag s,t=input(),input() m,n=len(s),len(t) count=0 for i in range(m-n+1): substr=s[i:i+n] if Similar(substr,t,n): count+=1 print(count) ac 83%

点赞回复分享

发布于 2018-09-09 21:25

Luoyin500

中国科学院大学算法工程师

也是83 #include <iostream> #include <vector> #include <map> using namespace std; int solve(string S,string T) { int num=0; for(int i=0;i<=int(S.size()-T.size());i++) { map<char,char> m1; map<char,char> m2; auto tmp=S.substr(i,T.size()); bool flag=true; for(int j=0;j<T.size();j++) { if(m1.count(tmp[j])) { if(m1[tmp[j]]!=T[j]) { flag=false; break; } } else { if(m2.count(T[j])) { if(m2[T[j]]!=tmp[j]) { flag=false; break; } } else { m1[tmp[j]]=T[j]; m2[T[j]]=tmp[j]; } } } if(flag) { num++; } } return num; } int main() { int res; string _S; getline(cin,_S); string _T; getline(cin,_T); res=solve(_S,_T); cout<<res<<endl; return 0; }

点赞回复分享

发布于 2018-09-09 21:29

Monrother

北京邮电大学算法工程师

同 python 75%，有 python AC 的吗？尤其 KMP 怎么设计转移函数？

点赞回复分享

发布于 2018-09-09 23:41