문자열 겹치기(구현, KMP)

단순한 문젠데 구현하는데 시간이 좀 걸렸던 것 같다. KMP를 통해 구현하면 좀 더 편하고 성능좋게 구현할 수 있지않을까 생각이 들었다. s1,s2의 길이가 100이라 일단 구현으로 풀었으나 KMP 문제 또한 풀어보며 해당 방식으로 구현해봐야겠다.

 

def solution(s1, s2):

    answer = ''

    pre = ""

    post = ""

    for i in range(len(s2)-1):

        pre+="!"

        post+="!"

    first = pre+s1+post

    

    

    lst = []

    for i in range(len(first)-len(s2)+1):

        s3 = ""

        t = 0

        fin = True

        left = False

        right = False

        for j in range(len(s2)):

            if first[i+j]!="!" and first[i+j]!=s2[j]:

                fin = False

                break

 

            if first[i+j]==s2[j]:

                t+=1

                s3+=s2[j]

            else:

                if first[i+j]=="!":

                    idx = (i+j)

                    if idx>=0 and idx<=len(s2)-1:

                        left=True

                    else:

                        right=True 

                    s3+=s2[j]    

            

        if fin:

            if left:

                for i in range(t,len(s1)):

                    s3+=s1[i]

            else:

                temp = ""

                for i in range(0,len(s1)-1):

                    temp+=s1[i] 

                s3= temp+s3 

 

            lst.append(s3)

        # print(s3)

        # print(t)

 

    mn_lst = 200

    for i in lst:

        if len(i)<mn_lst:

            mn_lst=len(i)

    lst.sort()

    for i in lst:

        if len(i)==mn_lst:

            answer=i

            break

 

    if s1==s2:  

        answer=s1

        

    return answer

 

a=solution("xyZA","ABCxy")

b=solution("AxA","AyA")

print(a)

print(b)