[백준] 1786번 찾기 (파이썬)

1786번: 찾기

 

 

코드

def find(pattern):
    lps = [0 for _ in range(len(pattern))]
    leng = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[leng]:
            leng += 1
            lps[i] = leng
            i += 1
        else:
            if leng != 0:
                leng = lps[leng - 1]
            else:
                lps[i] = 0
                i += 1

    return lps

def kmp(search, source):
    m = len(search)
    n = len(source)
    result = []
    lps = find(search)
    i = 0
    j = 0

    while i < n:
         if search[j] == source[i]:
             i += 1
             j += 1
             if j == m:
                 result.append(str(i-j+1))
                 j = lps[j - 1]

         else:
             if j != 0:
                 j = lps[j-1]
             else:
                 i += 1

    return result


def main():
    sourceString = input()
    searchString = input()
    result = kmp(searchString, sourceString)
    print(len(result))
    print(" ".join(result))

if __name__ == "__main__":
    main()