너와 나의 스토리

문제: https://www.acmicpc.net/problem/1305 문제 풀이: fail함수를 작성해서 prefix와 suffix가 일치하는 가장 긴 길이를 찾는다. 그 값을 광고판에 보이는 문자열 길이인 l에서 빼주면 된다. 여기서 중요한 점은 fail 함수에서 가장 큰 값을 빼주는 것이 아니라 맨 뒤를 기준으로 prefix와 suffix를 구해줘야 한다. 예를 들어, 입력으로 aaabaaadaa가 들어온다고 하자. fail[6]=3으로 가장 큰 값을 가지지만 결과는 맨 앞 뒤 aa만 겹치는 것으로 봐야 하므로 output은 8이다. 소스 코드: 더보기 #include #include #include #include #include #include #include #include #include ..

문제: https://www.acmicpc.net/problem/11585 문제 풀이: 첫 번째 문자열을 a라고 하고, 찾아야 할 문자열을 b라고 하자. a는 원형이기 때문에 a가 [abcd]라면 [abcdabc]로 만들어 준다. 그리고 kmp로 고기 먹을 수 있는 경우의 수를 구하고, gcd를 구해 나눠준 후 출력한다. 하지만 이렇게 하면 a 배열 크기를 두 배로 사용한다. 메모리를 많이 사용하고 싶지 않다면 [소스 코드 2] 풀이처럼 풀 수도 있다. * gcd 함수에서, else문에서 return으로 안하고 바로 gcd 호출하도록 했더니 런타임 에러가 났다 ㅎㅎ 댕청- 소스 코드 1: 더보기 #include #include #include #include #include #include #includ..

문제: https://www.acmicpc.net/problem/4354 문제풀이: 1. KMP의 fail 배열을 채움 2. 입력 들어온 문자열의 길이를 len이라고 할 때, #1 ababab -> len=6 -> fail[len-1] = 4 -> len-fail[len-1] = 2 // 2개가 -> len/(len-fail[len-1]) =3 // 3번 반복됨 #2 abcabcabc -> len=9 -> fail[len-1]=6 -> len-fail[len-1] = 3 // 3개가 -> len/(len-fail[len-1]) =3 // 3번 반복됨 ∴ 즉 정답은 len/(len-fail[len-1])임을 알 수 있다. BUT! abcabcab같은 경우 fail[len-1]함수가 1보다 크지만, 반복되는..