KMP 알고리즘에서 가장 좋은 경우의 최소 비교 수는 얼마입니까?

KMP 알고리즘에 대한 최상의 시나리오의 최소 비교 수는 얼마입니까?KMP 알고리즘에서 가장 좋은 경우의 최소 비교 수는 얼마입니까?

2012-10-20 Ansari

0, 검색중인 문자열이 비어 있으면 0입니다. 그것보다 더 좋은 시나리오는 생각할 수 없다. – rici

0 (n) 여기서 n은 텍스트의 길이이고 텍스트 길이는 0이므로 n = 0이됩니다. – Ansari

이 경우 분명히 0이지만 O (n)은 n과 동일하지 않습니다. 예를 들어, n + k (임의의 상수 k에 대해)는 O (n)입니다. O (n)은 제한에 관한 문장 일 뿐이며 n의 특정 값에 대한 설명은 아닙니다. 어떤 경우에도 KMP는 확실히 O (n)이지만 대부분의 시나리오에서 승수 (비교 횟수)는 1.0보다 약간 적습니다. – rici

글쎄, 가장 좋은 경우의 최소 비교 수는 문자열의 길이가 될 것입니다. 이는 첫 번째로 일치하는 것을 찾았 음을 의미합니다. 알고리즘은 O (n)입니다. 즉, 상한 또는 최악의 시나리오는 n 개의 비교를 취합니다. 여기서 n은 검색하는 문자열의 길이입니다. 위키는 꽤 좋습니다. http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

출처

2012-10-20 21:56:22 DaveyLaser

당신의 대답에서 얻은 것은 : T가 문자열이고 P가 패턴 인 경우, | T | = n, | P | = m 인 경우, 전체 교대 횟수가 최소 교대보다 S 인 경우 최소 교대는 1, 최소 교대는 n, 전체 교대 횟수는 O (n + S) O (n)보다 1이됩니다. 예를 들어, T = xxa이고 P = xx 일 경우 첫 번째 시도에서 1 개의 고지가 멈추고 총 비교는 3 (2는 'xx'이고 1은 불일치) ........ ... 내가 틀렸다면 나를 정정하십시오. – Ansari

예! :) 그 말이 맞아. – DaveyLaser

P가 두 문자로만 구성되어 있기 때문에 예제에는 불일치가 없습니다. – alestanis

찾고있는 문자열이 텍스트 문자열의 시작 부분에있을 때 가장 좋은 경우가 발생합니다. 이 경우 k 문자 문자열이 n 문자 문자열 안에 있으면 가장 좋은 비교 번호는 k입니다.

k 문자 단어를 기반으로 테이블을 계산하는 데 따른 오버 헤드를 고려해야합니다. 일치하는 단어가없는 경우 건너 뛸 문자를 알 수 있습니다. 어떤 경우에도이 구성은 O(k)에서 이루어집니다.

출처

2012-10-20 21:55:23 alestanis

다음과 같은 텍스트와 패턴이 있다고 가정 해보십시오. T = xxabc P = xx 이 경우 문자열 길이는 5이고 패턴 길이는 2이며 총 비교 수는 4입니다. O (m)와 같지 않음 – Ansari

4 가지 비교는 어디에 있습니까? T [0]을 P [0], T [1]을 P [1]과 비교하면 끝난다. – alestanis

KMP 알고리즘에서 가장 좋은 경우의 최소 비교 수는 얼마입니까?

답변

관련 문제