KMP

Đề bài: Cho xâu T, P độ dài <= 1e6. Tìm các vị trí xuất hiện xâu P trong T.

Code C++:

#include <iostream>
#include <cstring>
using namespace std;

int b[1000000 + 5];

int main() {
    string t, p;
    cin >> t >> p;
    
    int i = 0, j = -1;
    b[0] = -1;
    while(i < p.size()) {
        while(j >= 0 && p[i] != p[j]) j = b[j];
        i++; j++;
        b[i] = j;
    }
    
    i = 0; j = 0;
    while(i < t.size()) {
        while(j >= 0 && t[i] != p[j]) j = b[j];
        i++; j++;
        if (j == p.size()) {
            cout << i - j + 1 << ' ';
            j = b[j];
        }
    }
    
    return 0;
}

Độ phức tạp: O(length(T) + length(P))

Lưu ý: Code này đã được dùng để nộp bài SUBSTR trên SPOJ (http://vn.spoj.com/problems/SUBSTR/)

Ghi chú:
– Ý nghĩa mảng b: Xâu con 0..b[i]-1 trong P là tiền tố và đồng thời là hậu tố dài nhất của xâu con 0..(i-1) trong P. (Lưu ý P[b[i]] có thể giống hoặc khác P[i] )
Update 4/3/2017:
– Trạng thái kết thúc của KMP cho biết xâu con chung dài nhất là tiền tố của P và hậu tố của T
– Biến đếm j của xâu P chạy đến đâu có nghĩa là xâu con tiền tố độ dài j+1 của P có xuất hiện trong T

Happy coding,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s