이 문제를 해결하기 위해 일반적인 열거는 작동하지 않습니다. 그것의 점근선은
O(t*s)가 될 것입니다. 따라서 하위 문자열 검색 작업에는 KMP(Knuth-Morris-Pratt) 알고리즘을 사용합니다.
이 알고리즘을 구현하기 위해 문자열 접두사 함수가 사용됩니다. 이것은 길이
n (strong>s 길이)의 숫자 배열이며 각 요소는 최대 길이입니다. 접두사와 일치하는 하위 문자열
s의 가장 큰 자체 접미사입니다. 예:
<몸>
| 선 |
접두사 기능 |
참고 |
| 아바바캡 |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| 아바아브 |
0 1 0 1 2 2 3 |
|
O(n^3) 점근법을 사용한 간단한 접두사 함수 알고리즘:
벡터<정수> 접두사_함수(문자열 s) {
정수 n = (정수 ) s.길이();
벡터<정수>파이(n);
for (int i=0; i<n; ++i)
for (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
리턴파이;
}
이제 다음 형식의 문자열에 대한 접두사 함수를 만들어야 합니다. & nbsp; t + # + s, 여기서 #은 분명히 텍스트에 없는 구분 문자입니다. 해당 구분 문자 뒤에 접두사 함수의 값을 분석하면 결과 값이 원하는 하위 문자열의 길이와 같으면 해당 항목이 발견된다는 점에 유의해야 합니다. 예를 들어 "abababcab" 문자열의 경우 및 원하는 하위 문자열 "abab", 접두사 기능은 다음과 같습니다.
0 0 1 2 0 1 2 3 4 3 4 0 1 2 해당 문자열 s:
의 요소를 구문 분석해야 합니다.
1 2 3 4 3 4 0 1 2 - 값이 4( 4th 및 6th )인 두 가지 경우가 있습니다. 길이 t, 결과적으로 답을 작성해야 합니다. 4 - 4(길이 t) & nbsp; = 0 및 6 - 4 = 2. 이것이 정답이고 "abab"라는 문자열임을 알 수 있습니다. 실제로 "abababcab" 문자열의 하위 문자열입니다. 위치 0과 2.
접두사 기능을 최적화한 후(자세한 내용은 여기) O(n) 점근법을 사용하여 최종 알고리즘을 얻습니다.
벡터<정수> 접두사_함수(문자열 s) {
정수 n = (정수 ) s.길이();
벡터<정수>파이(n);
for (int i=1; i<n; ++i) {
int j = pi[i-1< /스팬>];
동안 (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
파이[i] = j;
}
리턴파이;
}
|
Z-함수
Z-함수 문자열 S - 배열 Z, 각 요소는 Z [i ]는 문자열 S의 위치 i에서 시작하는 하위 문자열의 가장 긴 접두어와 동일하며 전체 문자열 Z. 위치 0에 있는 Z 함수의 값은 일반적으로 0이거나 전체 문자열의 길이입니다.
난이도
O(|S| ^ 2)또는 O(|S|).
문자열 S - 배열 P의 Prefix 함수, P[i]의 각 요소는 전체 문자열 S의 접미사이기도 한 문자열 S의 위치 < code>i에서 시작하는 부분 문자열. 위치 0에 있는 P-함수의 값은 일반적으로 0이거나 전체 문자열의 길이입니다.
난이도
O(|S| ^ 2) 또는 O(|S|).
O(|S| ^ 2)에 대해 Z 기능 및 접두사 기능을 구현해 보세요. .
|
Z와 함수 접두사 모두 O(|S|)에서 문자열의 하위 문자열을 찾기 위한 KMP(Knuth-Morris-Pratt) 알고리즘을 구현하는 데 사용할 수 있습니다. 이 알고리즘의 본질은 다음과 같습니다. 검색하려는 문자열을 찾고자 하는 문자열에 귀속시킵니다. 이러한 줄 사이에 구분 문자, 즉 어떤 줄에도 나오지 않는 문자(보통 #)를 넣는 것이 매우 바람직합니다.
|