SPOJ SUBSTR

SUBSTR.cpp

// contest: http://vn.spoj.com/problems/SUBSTR/
// author: Nguyễn Minh Tuấn
// Đại Học Khoa Học Huế.

//->>>>>>>> Đặc biết chú ý: Bài này, mình sử dụng thuật toán KMP(Thuật toán Knuth–Morris–Pratt) để giải.. các bạn có thể tham
// khảo.

#include <bits/stdc++.h>

#define _for(i,a,b) for(int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define _it(i,v) for (typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define _all(v) v.begin(), v.end()

#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define sqr(x) ((x)*(x))
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s, t;
    cin >> s >> t;

    int n = s.length(), m = t.length();
    int* pit = new int[m+1];
    if(m >= 0) pit[0] = 0;
    if(m >= 1) pit[1] = 0;
    FOR(i, 2, m) { 
        for(int j = pit[i-1]; ;j = pit[j]) {
            if(t[j] == t[i-1]) { pit[i] = j + 1; break; }
            if(j == 0) { pit[i] = 0; break; }
        }
    }
    for(int i = 0, j = 0; i < n; ) {
        if(s[i] == t[j]) {
            i++; j++;
            if(j == m) {
                cout << i - m + 1 << ' ';
            }
        } else if(j > 0) {
            j = pit[j];
        } else i++;
    } delete[] pit;

    return 0;
}