algorithm
하위 문자열 검색
수색…
C 언어로 된 KMP 알고리즘
text txt 와 pattern pat이 주어지면이 프로그램의 목적은 pat의 모든 출현을 txt로 출력하는 것 입니다.
예 :
입력:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
산출:
Pattern found at index 10
입력:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
산출:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C 언어 구현 :
// C program for implementation of KMP pattern searching
// algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix
// values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j-1];
else
i = i+1;
}
}
free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // length of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the example
// AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
산출:
Found pattern at index 10
참고:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Rabin-Karp 알고리즘 소개
Rabin-Karp 알고리즘 은 Richard M. Karp 와 Michael O. Rabin 이 작성한 문자열 검색 알고리즘으로 해싱을 사용하여 텍스트의 패턴 문자열 집합 중 하나를 찾습니다.
문자열의 부분 문자열은 발생하는 또 다른 문자열입니다. 예를 들어 ver 은 stackoverflow 의 하위 문자열입니다. 커버 는 동일한 문자열의 하위 시퀀스이므로 하위 시퀀스와 혼동하지 마십시오. 즉, 문자열에서 연속되는 문자의 하위 집합은 주어진 문자열의 하위 문자열입니다.
Rabin-Karp 알고리즘에서 찾고자하는 패턴 의 해시를 생성하고 텍스트 의 롤링 해시가 패턴 과 일치하는지 확인합니다. 일치 하지 않으면 텍스트 에 패턴 이 존재하지 않음을 보증 할 수 있습니다. 그러나 일치하면 패턴 이 텍스트에 나타날 수 있습니다. 예제를 살펴 보겠습니다.
yeminsajid 우리는 패턴 NSA 텍스트에 존재하는지 확인하려면 :의 우리가 텍스트 있다고 가정 해 봅시다. 해시 및 롤링 해시를 계산하려면 소수를 사용해야합니다. 임의의 소수 일 수 있습니다. 이 예제에서는 prime = 11 을 취해 봅시다. 다음 수식을 사용하여 해시 값을 결정합니다.
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
우리는 다음을 나타냅니다 :
a -> 1 g -> 7 m -> 13 s -> 19 y -> 25
b -> 2 h -> 8 n -> 14 t -> 20 z -> 26
c -> 3 i -> 9 o -> 15 u -> 21
d -> 4 j -> 10 p -> 16 v -> 22
e -> 5 k -> 11 q -> 17 w -> 23
f -> 6 l -> 12 r -> 18 x -> 24
nsa 의 해시 값은 다음과 같습니다.
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
이제 텍스트의 롤링 해시를 찾습니다. 롤링 해시가 패턴의 해시 값과 일치하면 문자열이 일치하는지 확인합니다. 우리의 패턴은 3 글자이므로 우리의 텍스트에서 1 글자 3 글자를 가져 와서 해쉬 값을 계산할 것입니다. 우리는 얻는다 :
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
이 값은 패턴의 해시 값과 일치하지 않습니다. 그래서 문자열은 여기에 존재하지 않습니다. 이제 우리는 다음 단계를 고려해야합니다. 다음 문자열 emi 의 해시 값을 계산합니다. 수식을 사용하여이를 계산할 수 있습니다. 하지만 그건 다소 사소한 일이며 우리에게는 더 많은 비용이 듭니다. 대신 다른 기술을 사용합니다.
- 우리는 현재 해시 값에서 First String of First String 의 값을 뺍니다. 이 경우, y . 우리는
1653 - 25 = 1628얻습니다. - 차이를 소수로 나눕니다.이 예에서는 11 입니다. 우리는
1628 / 11 = 148얻습니다. - 우리는 새로운 문자 X (프라임) ᵐ-1을 추가합니다 . 여기서 m 은 패턴의 길이이고 몫은 i = 9 입니다.
148 + 9 X 11² = 1237됩니다.
새 해시 값이 패턴 해시 값과 같지 않습니다. 우리가 얻는 n 을 위해, 계속 전진해라.
Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806
일치하지 않습니다. 그 후, 초 동안, 우리가 얻을 :
Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462
일치하지 않습니다. 다음 으로 , 우리는 다음을 얻습니다.
Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344
그것은 일치! 이제 패턴을 현재 문자열과 비교합니다. 두 문자열이 모두 일치하므로이 문자열에 하위 문자열이 있습니다. 그리고 우리는 부분 문자열의 시작 위치를 반환합니다.
의사 코드는 다음과 같습니다.
해시 계산 :
Procedure Calculate-Hash(String, Prime, x):
hash := 0 // Here x denotes the length to be considered
for m from 1 to x // to find the hash value
hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash
해시 재 계산 :
Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash
문자열 일치 :
Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
if Text[i] is not equal to Pattern[i]
Return false
end if
end for
Return true
Rabin-Karp :
Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
Return i
end if
CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1
알고리즘이 일치하는 것을 찾지 못하면 단순히 -1을 반환합니다.
이 알고리즘은 표절을 탐지하는 데 사용됩니다. 소스 자료가 주어지면 알고리즘은 사례와 구두점과 같은 세부 사항을 무시하고 소스 자료의 문장에 대한 종이를 신속하게 검색 할 수 있습니다. 찾은 문자열이 풍부하기 때문에 여기서는 단일 문자열 검색 알고리즘을 실용적이지 않습니다. Knuth-Morris-Pratt 알고리즘 이나 Boyer-Moore String Search 알고리즘 은 Rabin-Karp 보다 빠른 단일 패턴 문자열 검색 알고리즘입니다. 그러나, 그것은 다중 패턴 검색을위한 선택 알고리즘입니다. k에서 고정 길이 패턴을 많은 수로 찾고자한다면 Rabin-Karp 알고리즘의 간단한 변형을 만들 수 있습니다.
길이가 n 인 텍스트와 결합 된 길이가 m 인 p 개의 패턴에 대한 평균 및 최고 사례 실행 시간은 공간 O (p) 에서 O (n + m) 이지만 최악의 시간은 O (nm) 입니다.
Knuth-Morris-Pratt (KMP) 알고리즘 소개
텍스트 와 패턴 이 있다고 가정하십시오. 패턴에 텍스트가 존재하는지 여부를 결정해야합니다. 예 :
+-------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
| Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+
| Index | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Pattern | b | c | g | l |
+---------+---+---+---+---+
이 패턴 은 텍스트에 존재 합니다 . 따라서 우리의 부분 문자열 검색은이 패턴이 시작되는 위치의 인덱스 인 3 을 반환해야합니다. 그러면 우리의 무차별 대입 부분 검색 절차는 어떻게 작동합니까?
우리가 일반적으로하는 일은 텍스트 의 0 번째 인덱스와 우리 패턴의 0 번째 인덱스부터 시작하여 Text [0] 과 Pattern [0]을 비교 합니다. 일치하지 않기 때문에 텍스트 의 다음 색인으로 이동하여 Text [1] 과 Pattern [0]을 비교 합니다. 이 값은 일치하므로 패턴 의 인덱스와 텍스트 의 인덱스도 증가시킵니다. 우리는 Text [2] 와 Pattern [1]을 비교 합니다. 그들은 또한 성냥이다. 앞서 언급 한 동일한 절차에 따라 Text [3] 과 Pattern [2]을 비교 합니다. 일치하지 않는 경우, 우리는 경기를 시작한 다음 순위부터 시작합니다. 그것은 텍스트 의 인덱스 2 입니다. 우리는 Text [2] 와 Pattern [0]을 비교 합니다. 일치하지 않습니다. 그런 다음 텍스트의 색인을 증가시켜 Text [3] 과 Pattern [0]을 비교 합니다. 그들은 일치한다. 다시 Text [4] 와 Pattern [1]이 일치하고, Text [5] 와 Pattern [2]가 일치하고 Text [6] 과 Pattern [3]이 일치합니다. 우리는 우리의 패턴의 끝에 도달 한 이후, 우리는 지금 우리의 일치 즉 3 시작되는 인덱스를 돌려줍니다. 패턴 이 : bcgll 이면 패턴에 텍스트 가 없으면 검색에서 예외 또는 -1 또는 기타 미리 정의 된 값을 반환해야합니다. 최악의 경우,이 알고리즘은 텍스트 의 길이를 m , 패턴 길이를 n 이라고 할 때 O(mn) 시간이 걸린다는 것을 분명히 알 수 있습니다. 이 시간 복잡성을 어떻게 줄일 수 있습니까? 여기에서 KMP 하위 문자열 검색 알고리즘이 제공됩니다.
크 누스 - 모리스 - 프랫 문자열 검색 알고리즘 또는 KMP 알고리즘은 불일치가 발생하면 단어 자체가 다음 일치 항목을 시작할 수있는 충분한 정보를 구현한다는 관찰을 사용하여 기본 "텍스트"에서 "패턴"의 발생을 검색합니다 따라서 이전에 일치 된 문자의 재검사를 건너 뜁니다. 이 알고리즘은 Donuld Knuth 와 Vaughan Pratt 가 1970 년에, 그리고 James H. Morris가 독자적으로 개발했습니다. 트리오는 1977 년 공동으로 출판했습니다.
더 나은 이해를 위해 예제 텍스트 와 패턴 을 확장 해 보겠습니다.
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+
처음에는 텍스트 와 패턴이 색인 2 와 일치합니다. 텍스트 [3] 과 패턴 [3] 이 (가) 일치하지 않습니다. 그래서 우리의 목표는이 본문 에서 거꾸로 돌아 가지 않는 것입니다. 즉, 불일치가 생길 경우, 우리가 매칭을 시작한 위치에서 우리의 매칭을 다시 시작하는 것을 원하지 않습니다. 이를 달성하기 위해 불일치가 발생하기 직전 패턴 에서 접미사 를 찾습니다 (substring abc ). 패턴 의 부분 문자열 접두사 이기도합니다. 이 예에서는 모든 문자가 고유하기 때문에 일치하는 하위 문자열의 접두사 인 접미사가 없습니다. 이것이 의미하는 바는, 우리의 다음 비교는 인덱스 0 에서 시작할 것입니다. 잠깐 만요, 왜 우리가 이것을했는지 이해하게 될 겁니다. 다음으로 Text [3] 과 Pattern [0] 을 비교하면 일치하지 않습니다. 그 후, 인덱스 4 에서 인덱스 9 까지의 텍스트 와 인덱스 0 에서 인덱스 5 까지의 패턴에 대해 일치하는 것을 찾습니다. 우리는 텍스트 [10] 과 패턴 [6] 의 불일치를 발견합니다. 불일치가 발생하는 지점 (부분 문자열 abcdabc ) 바로 전에 패턴 에서 부분 문자열을 가져온 다음 접미사를 확인합니다.이 접미사는이 부분 문자열의 접두사이기도합니다. 여기에서 ab 는이 하위 문자열의 접미사와 접두어입니다. 이것이 의미하는 바는, 우리가 Text [10] 까지 매치 되었기 때문에, 불일치하기 직전의 문자들은 ab 입니다. 우리는 그것에서 추론 할 것은 AB는 또한 우리가했다 문자열의 접두사이기 때문에, 우리가 다시 AB를 확인하지 않고 다음 검사가 텍스트에서 시작할 수 있다는 점이다 [10]과 패턴 [2]. 우리는 전체 본문을 되돌아 볼 필요가 없었습니다. 우리는 불일치가 발생한 곳에서 직접 시작할 수 있습니다. 이제 우리는 Text [10] 과 Pattern [2] 가 불일치하고, 불일치하기 전의 부분 문자열 ( abc )에도 접미사 인 접미사가 없기 때문에 Text [10] 와 Pattern [0]을 확인합니다 . 그들은 일치하지 않는다. 그 후 인덱스 11 에서 인덱스 17 까지의 텍스트 와 인덱스 0 에서 인덱스 6 까지의 패턴에 대한 텍스트 입니다. 텍스트 [18] 과 패턴 [7] 의 불일치를 발견했습니다. 그래서 다시 불일치하기 전에 부분 문자열을 검사하고 (substring abcdabc ) abc 가 접미사와 접두어 임을 확인합니다. 패턴 [7] 까지 매치 되었기 때문에, abc 는 Text [18] 보다 앞에 있어야합니다. 즉, 우리는 텍스트 [17] 와 텍스트 [18] 과 패턴 [3] 에서 비교가 시작될 때까지 비교할 필요가 없습니다. 따라서 우리는 경기를 찾을 것이고 우리는 경기의 시작 색인 인 15 를 반환 할 것입니다. KMP 하위 문자열 검색이 접미사 및 접두어 정보를 사용하여 작동하는 방식입니다.
이제 텍스트 와 패턴 사이에 문자가 일치하지 않으면 접미사가 접두사와 동일하고 어떤 시점에서 수표를 시작하는지 효율적으로 계산할 수 있습니다. 예제를 살펴 보겠습니다.
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
필요한 정보가 들어있는 배열을 생성합니다. 배열 S를 호출 해 봅시다. 배열의 크기는 패턴의 길이와 같습니다. 패턴 의 첫 문자는 임의의 접두사의 접미사가 될 수 없기 때문에, S [0] = 0을 붙이게됩니다. 우리는 처음에 i = 1 및 j = 0 을 취합니다. 각 단계에서 Pattern [i] 와 Pattern [j]를 비교 하고 i를 증가시킵니다. 일치가 있다면 우리는 S 넣어 [I] = J + 1 증분 J, 불일치가있는 경우, 우리는 J 경우 (제 j의 이전 값 위치 (사용 가능한 경우) 및 설정된 j 개의 =에서 S [J-1]을 확인 0 이 아닌 경우), S [j] 가 S [i] 와 일치하지 않거나 j 가 0 이 될 때까지 계속 수행합니다. 후자의 경우, 우리는 S [i] = 0을 넣는다. 예를 들면 다음과 같습니다.
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Pattern [j] 와 Pattern [i] 는 일치하지 않으므로 i 를 증가시키고 j 는 0 이므로 이전 값을 확인하지 않고 Pattern [i] = 0을 넣습니다. 우리는 I = 4, 난을 증가 유지하는 경우, 우리는 경기를 얻을 수 있습니다, 그래서 우리는 [I] =의 S [4] = J + 1 = 0 + 1 = 1, 증가 J와 나는 S를 넣어. 우리 배열은 다음과 같습니다.
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | | | |
+---------+---+---+---+---+---+---+---+---+
Pattern [1] 과 Pattern [5] 가 일치하기 때문에 S [i] = S [5] = j + 1 = 1 + 1 = 2를 넣는다. 계속하면 j = 3 및 i = 7에 대한 불일치를 발견하게됩니다. j 는 0 이 아니기 때문에, j = S [j-1]로 놓는다. 그리고 우리는 i 와 j 의 문자가 같거나 같지 않다는 것을 비교할 것입니다. 같은 것이기 때문에 S [i] = j + 1을 넣을 것입니다. 완성 된 배열은 다음과 같습니다 :
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
이것이 우리가 요구하는 배열입니다. 여기서 S [I]의 0이 아닌 값이 S의 [내가] + 1 개 위치로부터 개시 될 것을 문자열 (I 0 내지 문자열)의 프리픽스와 다음의 비교와 동일한 S [I] 길이 접미사가 의미 패턴 . 배열을 생성하는 알고리즘은 다음과 같습니다.
Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
if Pattern[i] is equal to Pattern[j]
S[i] := j + 1
j := j + 1
i := i + 1
else
if j is not equal to 0
j := S[j-1]
else
S[i] := 0
i := i + 1
end if
end if
end while
이 배열을 구축하기위한 시간 복잡도는 O(n) 이고 공간 복잡도는 O(n) 입니다. 완전히 알고리즘을 이해 한 경우 확인하려면 패턴에 대한 배열을 생성 할 aabaabaa 하고 결과와 일치하는 경우 확인 이 하나.
이제 다음 예제를 사용하여 부분 문자열 검색을 수행해 보겠습니다.
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Text | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| Pattern | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+
우리는 전에 정의 된 논리를 사용하여 텍스트 , 패턴 및 미리 계산 된 배열 S 를 가지고 있습니다. 텍스트 [0] 과 패턴 [0]을 비교하면 동일합니다. 텍스트 [1] 과 패턴 [1] 은 동일합니다. 텍스트 [2] 와 패턴 [2] 은 동일하지 않습니다. 우리는 불일치 직전의 위치에서 값을 확인합니다. S [1] 이 0 이기 때문에 우리의 부분 문자열에 접두사와 같은 접미사가 없으며 우리의 비교는 위치 S [1] 에서 시작됩니다. 이것은 0 입니다. 그래서 Pattern [0] 은 Text [2] 와 같지 않습니다. 그래서 우리는 계속 진행합니다. 텍스트 [3] 은 패턴 [0] 과 같으며 텍스트 [8] 과 패턴 [5] 까지 일치합니다. 우리는 S 배열에서 한 걸음 뒤로 가서 2를 찾습니다. 이것은 길이가 2 인 접두사가 있다는 것을 의미합니다.이 접미사는 ab 입니다.이 하위 문자열 ( abcab) 의 접미사이기도합니다. 그것은 또한 Text [8] 앞에 ab 가 있음을 의미합니다. 따라서 우리는 Pattern [0] 과 Pattern [1]을 안전하게 무시하고 Pattern [2] 와 Text [8] 에서 다음 비교를 시작할 수 있습니다. 우리가 계속하면, 우리는 텍스트의 패턴을 찾을 수 있습니다. 우리의 절차는 다음과 같습니다 :
Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
if Pattern[j] is equal to Text[i]
j := j + 1
i := i + 1
if j is equal to n
Return (j-i)
else if i < m and Pattern[j] is not equal t Text[i]
if j is not equal to 0
j = S[j-1]
else
i := i + 1
end if
end if
end while
Return -1
접미어 배열 계산과 별개로이 알고리즘의 시간 복잡도는 O(m) 입니다. GenerateSuffixArray 는 O(n) 취하므로 KMP 알고리즘의 총 시간 복잡도는 O(m+n) 입니다.
추신 : 당신이 텍스트 에서 Pattern 을 여러 번 찾으려면 값을 반환하는 대신 print / store하고 j := S[j-1] . 또한 발생을 발견했는지 여부를 추적하고 그에 따라 처리하는 flag 를 유지하십시오.
KMP 알고리즘의 파이썬 구현.
Haystack : 주어진 패턴을 검색해야하는 문자열.
Needle : 검색 할 패턴.
시간 복잡성 : 검색 부분 (strstr 방법)은 복잡성이 있습니다. 여기서 n 은 건초 더미의 길이입니다. 바늘은 프리픽스 테이블 작성을 위해 미리 파싱됩니다. O (m)은 접두사 테이블 작성에 필요합니다. 여기서 m 은 길이입니다. 바늘.
따라서, KMP에 대한 전체 시간 복잡도는 O (n + m)
공간 복잡성 : 바늘의 접두사 테이블 때문에 O (m) .
참고 : 구현 다음에 haystack (일치하는 경우)의 일치 시작 위치가 반환됩니다. needle / haystack이 빈 문자열이거나 haystack에서 바늘을 찾을 수없는 경우와 같이 가장자리의 경우 -1이 반환됩니다.
def get_prefix_table(needle):
prefix_set = set()
n = len(needle)
prefix_table = [0]*n
delimeter = 1
while(delimeter<n):
prefix_set.add(needle[:delimeter])
j = 1
while(j<delimeter+1):
if needle[j:delimeter+1] in prefix_set:
prefix_table[delimeter] = delimeter - j + 1
break
j += 1
delimeter += 1
return prefix_table
def strstr(haystack, needle):
# m: denoting the position within S where the prospective match for W begins
# i: denoting the index of the currently considered character in W.
haystack_len = len(haystack)
needle_len = len(needle)
if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
return -1
prefix_table = get_prefix_table(needle)
m = i = 0
while((i<needle_len) and (m<haystack_len)):
if haystack[m] == needle[i]:
i += 1
m += 1
else:
if i != 0:
i = prefix_table[i-1]
else:
m += 1
if i==needle_len and haystack[m-1] == needle[i-1]:
return m - needle_len
else:
return -1
if __name__ == '__main__':
needle = 'abcaby'
haystack = 'abxabcabcaby'
print strstr(haystack, needle)