1 |
1
주어진 서열로부터 전위부(u)와 상보적으로 결합되는 매칭 전위부의 길이가 후위부(x)와 상보적으로 결합되는 매칭 후위부의 길이보다 짧다고 가정한 상태에서 상기 서열의 위치 i에서 상보적 결합 조건 및 길이 조건을 만족하는 가장 긴 u의 길이인 c[i]와 상보적 결합 조건은 만족하나 길이 조건을 만족하지 못하는 가장 짧은 u의 길이인 c'[i]를 출력하는 매칭 전위부 탐색부;주어진 서열로부터 후위부(x)와 상보적으로 결합되는 매칭 후위부의 길이가 전위부(u)와 상보적으로 결합되는 매칭 전위부의 길이보다 짧다고 가정한 상태에서 상기 서열의 위치 i에서 상보적 결합 조건 및 길이 조건을 만족하는 가장 긴 x의 길이인 d[i]와 상보적 결합 조건은 만족하나 길이 조건을 만족하지 못하는 가장 짧은 x의 길이인 d'[i]를 출력하는 매칭 후위부 탐색부; 및상기 c[i]
|
2 |
2
제1항에 있어서,상기 매칭 전위부 탐색부는 i=(n-1)부터 감소시키면서 상기 c[i] 및 c'[i]를 연산하며, i+1위치에서 상보적 결합이 있다고 판단되는 경우 상기 c[i] 및 상기 c'[i]는 s=c[i+1] 및 p=c'[i+1]에 기초하여 연산되고, n은 주어진 서열의 길이인 것을 특징으로 하는 유사매듭구조 탐색 장치
|
3 |
3
삭제
|
4 |
4
제2항에 있어서,상기 길이 조건은 주어진 서열의 길이가 n일 경우 i-s≥s+1 및 n-i-s-1≥s+1인 것을 특징으로 하는 유사매듭구조 탐색 장치
|
5 |
5
제4항에 있어서,i 위치에서 연속적인 상보적 결합 조건은 만족하나 상기 길이 조건을 만족하지 않을 경우, s-1 위치에서의 넥스트 함수값을 이용하여 상기 s의 사이즈를 축소시킨 후 상기 연속적인 상보적 결합 조전과 상기 길이 조건을 판단하며, 상기 넥스트 함수는 i에서 끝나는 서브스트링 중 주어진 서열 w의 전위부가 되는 가장 긴 서브스트링의 길이인 것을 특징으로 하는 유사매듭구조 탐색 장치
|
6 |
6
제5항에 있어서,i 위치에서 상기 연속적인 상보적 결합 조건은 만족하나 상기 길이 조건을 만족하지 않을 경우, 상보적 결합 조건을 마지막으로 만족했던 p를 찾아내 c'[i]=p+1로 설정하고 p=p+1로 업데이트하는 것을 특징으로 하는 유사매듭구조 탐색 장치
|
7 |
7
제1항에 있어서,상기 유사매듭구조 결정부는 , (d[i], c[i+1]), (d'[i], c[i+1]) 및 (d[i], c'[i+1])의 조합 중 길이 조건을 만족하면서 u의 길이 및 x의 길이의 최소값 중 가장 긴 길이를 가지는 조합을 주어진 서열의 유사매듭구조로 결정하는 것을 특징으로 하는 유사매듭구조 탐색 장치
|
8 |
8
주어진 서열로부터 전위부(u)와 상보적으로 결합되는 매칭 전위부의 길이가 후위부(x)와 상보적으로 결합되는 매칭 후위부의 길이보다 짧다고 가정한 상태에서 상기 서열의 위치 i에서 상보적 결합 조건 및 길이 조건을 만족하는 가장 긴 u의 길이인 c[i]와 상보적 결합 조건은 만족하나 길이 조건을 만족하지 못하는 가장 짧은 u의 길이인 c'[i]를 출력하는 매칭 전위부 탐색 단계(a);주어진 서열로부터 후위부(x)와 상보적으로 결합되는 매칭 후위부의 길이가 전위부(u)와 상보적으로 결합되는 매칭 전위부의 길이보다 짧다고 가정한 상태에서 상기 서열의 위치 i에서 상보적 결합 조건 및 길이 조건을 만족하는 가장 긴 x의 길이인 d[i]와 상보적 결합 조건은 만족하나 길이 조건을 만족하지 못하는 가장 짧은 x의 길이인 d'[i]를 출력하는 매칭 후위부 탐색 단계(b); 및상기 c[i]
|
9 |
9
제8항에 있어서,상기 단계(a)는 i=(n-1)부터 감소시키면서 상기 c[i] 및 c'[i]를 연산하며, i+1위치에서 상보적 결합이 있다고 판단되는 경우 상기 c[i] 및 상기 c'[i]는 s=c[i+1] 및 p=c'[i+1]에 기초하여 연산되는 것을 특징으로 하는 유사매듭구조 탐색 방법
|
10 |
10
제9항에 있어서,상기 길이 조건은 주어진 서열의 길이가 n일 경우 i-s≥s+1 및 n-i-s-1≥s+1인 것을 특징으로 하는 유사매듭구조 탐색 방법
|
11 |
11
제10항에 있어서,i 위치에서 연속적인 상보적 결합 조건 및 상기 길이 조건을 만족할 경우 c[i]=s+1로 설정되고, s=s+1로 업데이트되는 것을 특징으로 하는 유사매듭구조 탐색 방법
|
12 |
12
제11항에 있어서,i 위치에서 상기 연속적인 상보적 결합 조건은 만족하나 상기 길이 조건을 만족하지 않을 경우, s-1 위치에서의 넥스트 함수값을 이용하여 상기 s의 사이즈를 축소시킨 후 상기 연속적인 상보적 결합 조건과 상기 길이 조건을 판단하며, 상기 넥스트 함수는 i에서 끝나는 서브스트링 중 주어진 서열 w의 전위부가 되는 가장 긴 서브스트링의 길이인 것을 특징으로 하는 유사매듭구조 탐색 방법
|
13 |
13
제12항에 있어서,i 위치에서 상기 연속적인 상보적 결합 조건은 만족하나 상기 길이 조건을 만족하지 않을 경우, 상보적 결합 조건을 마지막으로 만족했던 p를 찾아내 c'[i]=p+1로 설정하고 p=p+1로 업데이트하는 것을 특징으로 하는 유사매듭구조 탐색 방법
|
14 |
14
제8항에 있어서,상기 단계(c)는 (d[i], c[i+1]), (d'[i], c[i+1]) 및 (d[i], c'[i+1])의 조합 중 길이 조건을 만족하면서 u의 길이 및 x의 길이의 최소값 중 가장 긴 길이를 가지는 조합을 주어진 서열의 유사매듭구조로 결정하는 것을 특징으로 하는 유사매듭구조 탐색 방법
|
15 |
15
제8항 내지 제14항 중 어느 한 항의 방법을 실행하기 위한 프로그램이 기록되어 있으며 컴퓨터에 의한 판독 가능한 프로그램이 기록된 기록매체
|