KMP
Bài toán
In ra tất cả vị trí xuất hiện của một pattern trong xâu.
Độ phức tạp
O(m+n)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1000006;
int m, n, Prev[N];
char a[N], b[N];
int main() {
scanf("%s%s", a + 1, b + 1);
m = strlen(a + 1), n = strlen(b + 1);
Prev[0] = -1;
for (int i = 1; i <= n; i++) {
Prev[i] = 0;
for (int j = Prev[i - 1]; j != -1; j = Prev[j])
if (b[j + 1] == b[i]) {
Prev[i] = j + 1;
break;
}
}
int u = 0;
for (int i = 1; i <= m; i++) {
while (u != 0 && b[u + 1] != a[i]) u = Prev[u];
if (b[u + 1] == a[i]) u++;
if (u == n) printf("%d ", i - n + 1);
}
puts("");
}
Nhận xét
Mô tả
int Prev[]
Prev[i]=x nếu x kí tự đầu tiên trong xâu b[1..i] bằng x kí tự cuối cùng trong xâu b[1..i]. Prev[i] có tính chất: b[i]=b[Prev[i]] với quy ước b[0]=b[i] với tất cả các i. Prev ngoài ra có thể được sinh như sau:
Prev[i]=Prev[i-1]+1
nếu b[i] bằng b[Prev[i]] thì in ra Prev[i]
Prev[i]=Prev[Prev[i-1]]+1
nếu b[i] bằng b[Prev[i]] thì in ra Prev[i]
Prev[i]=Prev[Prev[Prev[i-1]]]+1
....
Tham khảo
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm