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