SPOJ PSTRING

pstring.cpp

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

const int INF = 1<<30;

int M[10005][1005], n, m, pi[1005], c;
int A[1005], B[1005], savej[1005];
string T, P;
//char T[10005], P[1005];

//inline void kmpPreprocess(char P[]) {
inline void kmpPreprocess(string &P) {
    int i = 0, j = -1;
    pi[0] = -1;
    while(i < m) {
        while(j>=0 and P[i] != P[j])
            j = pi[j];
        i ++, j++;
        pi[i] = j;
    }
}

#define mini(a,b) a<b?a:b

int main() {
    while(cin>>T>>P) {
        //memset(M, -1, sizeof M);
        //n = strlen(T), m = strlen(P);
        n = T.size(), m = P.size();
        kmpPreprocess(P);
        //printf("%d\n", DP(0, 0));
        B[m] = INF;
        for(int i=0; i<m; i++)
            B[i] = 0;
        for(int i=n-1; i>=0; i--) {
            A[m] = INF;
            for(int j=0, jj; j<m and j<=i; j++) {
                savej[j] = pi[j];
                A[j] = 1+B[j];
                jj = j;
                while(jj>=0 and T[i]!=P[jj])
                    jj = savej[jj];
                savej[j] = jj;
                A[j] = mini(A[j],B[jj+1]);
            }
            for(int j=0, jj; j<m and j<=i; j++)
                B[j] = A[j];
        }
        //printf("# %d\n", c);
        printf("%d\n", A[0]);
    }
}