kmp.cpp

Đã có code sử dụng zero-based ở bên dưới.

Bài toán

Cho một xâu t và một từ s. Tìm các vị trí xuất hiện từ s trên xâu t.

Độ phức tạp

O(m+n)

với m, n là độ dài hai xâu s và t

Code này của : Nguyễn Thành Trung

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

using namespace std;

const int MN = 1000111;

char s[MN], t[MN];

int nxt[MN];

int main() {

    scanf("%s\n", &t[1]);

    scanf("%s\n", &s[1]);

    int j;

    j = nxt[1] = 0;

    for (int i = 2; s[i]; ++i) {

        while (j > 0 && s[j + 1] != s[i]) j = nxt[j];

        if (s[j + 1] == s[i]) ++j;

        nxt[i] = j;

    }

    j = 0;

    for (int i = 1; t[i]; ++i) {

        while (j > 0 && s[j + 1] != t[i]) j = nxt[j];

        if (s[j + 1] == t[i]) ++j;

        if (s[j + 1] == 0) {  // Het xau s

            printf("%d ", i - j + 1);

            j = nxt[j];

        }

    }

    puts("");

    return 0;

}

Nhận xét

Bài toán này có thể dùng Hash để xử lý nhưng Hash vẫn có xác suất sai. Trong khi KMP là thuật toán chuẩn.

Cảm ơn anh Nguyễn Thành Trung đã giúp em hoàn thành bài viết này.

Mô tả

next

next[i]=x nếu x kí tự đầu tiên trong xâu s[1..i] bằng x kí tự cuối cùng trong xâu s[1..i]. next[i] có tính chất: s[i]=s[next[i]] với quy ước s[0]=s[i] với tất cả các i. next ngoài ra có thể được sinh như sau:

next[i]=next[i-1]+1

nếu s[i] bằng s[next[i]] thì in ra next[i]

next[i]=next[next[i-1]]+1

nếu s[i] bằng s[next[i]] thì in ra next[i]

next[i]=next[next[next[i-1]]]+1

....