Sunday, March 6, 2016

SPOJ PSTRING (KMP + DP (Recursive)) Solution C++

Problem : www.spoj.com/problems/PSTRING

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));
}
}```