전체 글 (704) 썸네일형 리스트형 kmp. [13506] [1. 문제 설명] https://www.acmicpc.net/problem/13506 [2. 풀이 접근] 고찰 아래 코드에서 H 에 해당하는 부분을 for 문 안에서 구하면 시간 초과 발생. 물론 이 때는, postfix 만큼을 원래 문자열 S 에서 제거하여 생성하였음. 부분 문자열을 만드는데 걸리는 시간이 선형 시간이라서? prefix 와 postfix 를 만들 때 에도 비슷하게 걸릴 거 같긴 한데, [3. 코드] kmp. [7575] [1. 문제 설명] https://www.acmicpc.net/problem/7575 [2. 풀이 접근] 임의의 프로그램에 대해서, 발생 할 수 있는 K 개의 모든 코드를 구하고, 이 코드를 나머지 프로그램에서 찾는다. 문제에서는 코드 길이가 K 이상인 경우에도 바이러스라고 판정가능하다 하였는데, 사실 K 개만 일치하면, K개 보다 큰 경우에 대해서 코드 일치 여부와 관계 없이 바이러스 코드로 추정 할 수 있다. # K+1 개, 일치 => K 개가 일치하므로 상관 없다. # K+1 개. 불일치 => 역시 K 개는 일치하므로 상관 없다. 일종의 함정인 셈 # K=4 라고 하면, # K=5 코드, K=6 코드를 구할 필요가 없다. 연산 횟수를 대강 계산하면, 생성할 수 있는 코드 개수 : 1000개 (정확하.. kmp. [11585] [1. 문제 설명] https://www.acmicpc.net/problem/11585 [2. 풀이 접근] kmp search 원형에 대해서 문자열을 이어 붙이고, 이 문자열에서 다른 문자열을 찾는 전형적인 kmp 탐색 문제이다. 주의 할 점 주석에도 언급했지만, 이어붙인 문자열 X=2B 에 대해서 X[len(B)...] 에서 A 를 찾는 것은 의미가 없다. 기약 분수 분자와 분모의 최대공약수를 찾아야 한다. 유클리드 호제법을 이용하여 계산하도록 한다. 생각이 안나서 과거에 정리한 글을 참조 https://testkernelv2.tistory.com/107 [3. 코드] 이전 1 ··· 42 43 44 45 46 47 48 ··· 235 다음