글 읽기 - 4206 반례/로직 질문

(追記) (追記ここまで)

4206 반례/로직 질문

4206번 - 피보나치 단어

dahyun1226 5년 전 0

kmp를 사용했고, F를 20만보다 커졌을 때 10만씩 떼서 최대 20만으로 길이를 고정해놓고 풀었습니다.

dp는 그냥 dp[i] += kmp(F[i], bits) - dp[i - 1] - dp[i - 2]로 해결했습니다.

63퍼 정도에서 막혔습니다.

기본 테스트케이스나 확인해볼만한 애들은 통과했다고 생각합니다.

어떤 로직이 틀렸을까요?

# 백준 온라인 저지 4206반: 피보나치 단어
def makeFail(n: str):
 fail = [0] * len(n)
 matched = 0
 for index in range(1, len(n)):
 while n[matched] != n[index] and matched > 0:
 matched = fail[matched - 1]
 if n[matched] == n[index]:
 matched += 1
 fail[index] = matched
 return fail
def kmp(h: str, n: str):
 fail = makeFail(n)
 matched = 0
 result = []
 for index in range(0, len(h)):
 while matched > 0 and h[index] != n[matched]:
 matched = fail[matched - 1]
 if h[index] == n[matched]:
 matched += 1
 if matched == len(n):
 result.append(index - matched + 1)
 matched = fail[matched - 1]
 return len(result)
F = ["0"] * 101
F[1] = "1"
for i in range(1, 28):
 F[i + 1] = F[i] + F[i - 1]
 # 28 27은 20만 넘는다.
for i in range(29, 101):
 F[i] = F[i - 1][:100000] + F[i - 2][-100000:]
tc = 1
while True:
 try:
 dp = [0] * 101
 n = int(input())
 bits = input()
 if bits == '0': dp[0] = 1
 if bits == '1': dp[1] = 1
 for i in range(2, n + 1):
 dp[i] = dp[i - 1] + dp[i - 2]
 if i <= 28:
 dp[i] += kmp(F[i], bits) - dp[i - 1] - dp[i - 2]
 elif i >= 29:
 dp[i] += kmp(F[i][-len(bits) + 1:] + F[i][:len(bits) - 1], bits)
 print("Case " + str(tc) + ": " + str(dp[n]))
 tc += 1
 except EOFError:
 break