분류 전체보기
-
백준 4354 문자열 제곱Algorithm/BOJ(백준) 2018. 9. 6. 23:43
문제 링크 : https://www.acmicpc.net/problem/4354※선행해야 할 알고리즘 : KMP Algorithm 1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음. 2. 다음 예제 입력 문자열들의 patterntable값을 구하면 다음과 같다.string patterntable[string.size()-1] abcd 0 aaaa 3 ababab 4 하지만, 문제가 원하는 값은 패턴 문자열들의 개수를 구하는 것임으로 다음과 같다.string패턴 문자열패턴 문자열의 개수 abcd abcd1aaaaa4abababab3 첫번째와 두번째는 패턴 문자열이 없거나 ..
-
백준 1305 광고Algorithm/BOJ(백준) 2018. 9. 6. 21:23
문제 링크 : https://www.acmicpc.net/problem/1305※선행해야 할 알고리즘 : KMP Algorithm Algorithm : 문자열의 pattern table을 구한 후 그 해당하는 pattern table값을 문자열 길이에서 빼준다. 1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음. 2. 예를 들어aabaaa에서 보면 pi=2, prefix suffix가 같은 최대의 부분 문자열이 aa이다. 길이가 N인 광고가 계속 이어져 있는 것을 생각하면 prefix aa는 앞 광고의 suffix aa로 볼 수도 있을 것이다. 즉, baaa가 원래 광고..