Problem : www.spoj.com/problems/PSTRING

1. Compute KMPs DFA.

2. Apply DP.

i) Either include a character or skip it.

ii) Skip a character if it leads to a full substring match.

**Algorithm :**1. Compute KMPs DFA.

2. Apply DP.

i) Either include a character or skip it.

ii) Skip a character if it leads to a full substring match.

**Code:**#include <iostream> #include <cassert> #include <string.h> using namespace std; const int mx = 10011 , my = 1024; int f[my] , trans[my][26]; char X[mx] , Y[my], c ; int dp[my][mx],xlen,ylen, inf = 1<<30; #define mini(x, y) (x)<(y)?(x):(y) int recurse(int matchedLength, int ind){ if(ind==xlen)return 0; if(dp[matchedLength][ind]!=-1)return dp[matchedLength][ind]; int ret1=inf, ret2=inf, ans=0;

int currentMatched = trans[matchedLength][X[ind]-'a']; if(currentMatched==ylen){ ret2 = 1+recurse(currentMatched-1, ind+1); }else ret2 = recurse(currentMatched, ind+1);

```
ret1 = 1+recurse(matchedLength, ind+1);
if(ret1==0)ret1 = inf;
```

ans = mini(ret1, ret2); dp[matchedLength][ind] = ans; return ans; } int main() { int k,i,j; while (gets(X)) { gets(Y); xlen = strlen(X) , ylen = strlen(Y);

k=0;f[0]=0;

for(i=1;i<ylen;++i){ while(k>0 && Y[i]!=Y[k])k = f[k-1]; if(Y[i] == Y[k])k++; f[i] = k; }

for(i=0;i<my;++i)for(j=0;j<mx;++j)dp[i][j]=-1; for(i=0;i<ylen;++i){ for(c='a';c<='z';++c){ k = i; while(k>0 && Y[k] != c)k = f[k-1]; if(Y[k] == c)k++; trans[i][c-'a'] = k; } } printf("%d\n", recurse(0, 0)); } }