초록 close

단백질의 구조를 예측하는 과정에 사용될 수 있는 다음 문제를 고려한다. 길이가n이고 원소가 모두 양수인 두 배열 A, B 와 양수 M 이 주어질 때, A[i]+...+ A[j] + B[k] +...+ B[l] = M 이 되는 부배열 쌍 A[i] ,..., A[j], 1≤i≤j≤n 과 B[k] ,..., B[l], 1≤k≤l≤n 을 모두 찾으시오. 본 논문에서는 O(n²log n + K) 이 문제를 O(n) 시간에 메모리를 사용하여 해결하는 알고리즘을 제시한다. 단, K 는 찾은 부배열 쌍의 수이다. 기존의 결과는 O(n²log n + K log n) 시간과 O(n) 메모리였다.


We are considering the following problem that can be used in the prediction of the structure of proteins. Given two length n arrays A , B with positive numbers and a positive number M , find all pairs of subarrays A[i] ,..., A[j], 1≤i≤j≤n , and B[k] ,..., B[l], 1≤k≤l≤n , such that A[i]+...+ A[j] + B[k] +...+ B[l] = M . This paper presents an algorithm with time using memory, where is the number of pairs output. The previously best known one is with time and memory.