[python] 백준 2195 문자열 복사

https://www.acmicpc.net/problem/2195

2195번: 문자열 복사

 

문제 해결

• S에서 P로 가는 경우의 수를 찾는 것보다 P에서 S로 가는 경우를 찾는 것이 더 편하다. (문자열 하나의 기본 전략인 듯)
• 그러면 P에서 일부분이 S의 안에 있으면 +1을 해주면 될 것이다. 대신 최대한 문자열 길이를 길게 끊어야 한다.
• 문자열이 S안에 포함이 안될 때 까지 계속 이어 붙인다. 포함이 안되면 거기서 끊고 ans을 +1 해주고 인덱스는 다시 거기서 부터 시작해서 새로운 문자열을 만들어 S안에 있는지 확인한다.

 

CODE

S = str(input())
P = str(input())
ans = 0
idx = 0
while idx < len(P):
    copy = ''
    if S.find(P[idx:]) != -1:
        ans += 1
        break
    for j in range(idx, len(P)):
        copy += P[j]
        if S.find(copy) == -1:
            ans += 1
            idx = j
            break
print(ans)