BOJ 2401 - 최대 문자열 붙여넣기

문제 : https://www.acmicpc.net/problem/2401

각각의 짧은 문자열들이 긴 문자열에서 어디에 등장하는지만 알 수 있다면, 이 문제는 전형적인 다이나믹 프로그래밍 문제가 된다. 그러니깐 KMP를 돌리면서 테이블을 채우면 된다.
시간 복잡도는 긴 문자열 길이 $S$, 짧은 문자열 길이 $T$, 짧은 문자열의 수 $N$이라 할때 $O(N * (S + T))$가 된다.

코드 : http://ideone.com/zloOUb

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

파이썬 재귀 최대깊이 지정 sys.setrecursionlimit( limit )

https://docs.python.org/2/library/sys.html#sys.setrecursionlimit https://www.acmicpc.net/problem/1012 파이썬 써본지 얼마 안되서 DFS를 구현하는 문제를 풀었는데 알고리즘상에 문제가 없어보이는데 자꾸 오답이 나왔다. 무슨 문젠가 몇시간 동안 고민했는데 이유는 재귀깊이 한계치가 작아서였다. import sys sys.setrecursionlimit(10**6) 을 추가해줬더니 정답처리 됐다. import sys sys.setrecursionlimit( 10 * * 6 ) bat = [] dx = [ 0 , 1 , 0 , - 1 ] dy = [ 1 , 0 , - 1 , 0 ] M = N = K = 0 def dfs ( x , y ): bat[x][y] = 0 for k in range ( 4 ): i = x + dx[k] j = y + dy[k] if (i >= M or i < 0 or j >= N or j < 0 ): continue if (bat[i][j] == 1 ): dfs(i,j) return for t in range ( input ()): (M,N,K) = map ( int , raw_input ().split()) cnt = 0 bat = [[ 0 for j in range (N + 1 )] for i in range (M + 1 )] for i in range (K): (a,b) = map ( int , raw_input ().split()) bat[a][b] = 1 for i in range (M): for j in range (N): if
계속 읽기