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

KMP Substring Match Algorithm (LPS array/Multiple Occurences) - Java

There is another implementation that uses 2D array for transition table of a DFA. Link

Read this first : http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

Example case:

text: aaabacaabaazq
pat : aabaax

       a a b a a x
lps : [0 1 0 1 2 0]

j = pat index
i = txt index

What do lps values mean?

lps values at any index indicate where in (at what index) we should go in pat so
that our search for the pattern continues in case a mismatch occurs in the middle of successful matching.
If a mismatch occurs at index j in pat, we consider pat[j-1] as the index in pattern string which should be matched next.
Think about prefix suffix match (the tutorial link above) and you'll get the intuition.

For example, if we have matched upto "aa"a in txt 
                                 and "aa"b in pat.

Now the next character is different in both strings (j = 2, i = 2). So we look at lps[j-1] = lps[2-1] = lps[1] = 1.
It means we need to resume our search again at index 1 in pat with the current value of i=2.

Lets see what is at index 1 in pat and index 2 in txt. 

         M
     0 1 2 3 4 5 6 7 8 9
txt: a a a b a c a a b a a z q
pat: a a b a a x

This is good as we did not go to index 1 if we were using bruteforce. We reused the already done computation i.e.
aa in the pat matches upto index 2 in text (beginning at index 1). So we start again at index 3 in txt and index 2 in pat.

Now consider that we already processed
                   |
text: aaabac"aabaa"zq 
pat:  "aabaa"x
             |

so i = 11, j = 5, the indices we are considering now.
A mismatch!, so now look at lps[j-1] = lps[4] = 2
That means we can resume our search with current i the same = 11 and j = 2.
Now we match characters at i = 11, j = 2 in their respective strings.

z!=x.
A mismatch again. But we saved the time for looking at 2 characters "aa"baax in aabaax. If it were bruteforce, we would have
started matching again from the beginning at index 7 in text and index 0 in pat. But now it is index 11 in text and index 2 in pat
that we are matching.

Source :

public class KMPOD {
    static int[] lps;
    static int[] locations;
    
    public static int[] lps(String pat){
        lps = new int[pat.length()];
        
        int i=1, len=0, L = pat.length();
        while(i<L){
            if(pat.charAt(i)==pat.charAt(len)){
                len++;
                lps[i] = len;
                i++;
            }else{
                if(len!=0){
                    len = lps[len-1];
                }else{
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    
    public static int[] match(String txt, String pat){
        locations = new int[txt.length()+1];
        int z=1;
        
        int M = pat.length();
        int N = txt.length();
        
        lps(pat);
        
        int j = 0;
        int i = 0;
        
        while(i<N){
            if(pat.charAt(j) == txt.charAt(i)){
                j++;i++;
            }
            if(j==M){
                locations[z++]=(i-j);
                locations[0]++;         //0th index to store the size
                j = lps[j-1];
            }else if(i<N && pat.charAt(j) != txt.charAt(i)){
                if(j!=0) j = lps[j-1];
                else i++;
            }
        }
        return locations;
    }
    
    public static void main(String[] args){
        String text = "aneedleinahaystackneedlehereanotherneedlehere";
        String pat = "needle";
        int[] res = match(text, pat);
        for(int i=1;i<=res[0];++i){
            System.out.println("Match at Index : "+res[i]);
        }
    }
}

Output:

Match at Index : 1
Match at Index : 18
Match at Index : 35

ARDA1 SPOJ (Bruteforce / KMP) Solution C++

Bruteforce / KMP

With bruteforce - 0.01s

With KMP        - 0.17s

Solution (Bruteforce):

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std; 

char s[301][301];
char world[2001][2001]; 

int main(){
 int a, b;  
 scanf("%d %d", &a, &b);  
 for(int i=0;i<a;++i){scanf(" %s", s[i], sizeof(char)*b);}
 int x, y;
 scanf("%d %d", &x, &y); 
 for(int i=0;i<x;++i){scanf(" %s", world[i], sizeof(char)*y);}

 bool g = false; 

 for(int i=0;i<=x-a;++i){
  for(int j=0;j<=y-b;++j){

   if(world[i][j]==s[0][0]){
    bool f = true;
    for(int n=0, i2 = i;i2<i+a;++n, ++i2){
     for(int m=0, j2 = j;j2<j+b;++j2, ++m){
      if(s[n][m]!=world[i2][j2]){
       f = false;break;
      } 
     }
    }
    if(f){
     g = true;
     printf("(%d,%d)\n", i+1, j+1);
    } 
   }  
  } 
 }
 if(!g)printf("NO MATCH FOUND...\n"); 
 return 0;
}

Solution (KMP):

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

vector<int> indices;
class KMPSubstringMatch{
public:
 int W, R;
 int **dfa;
 char *s, *sub; 

 KMPSubstringMatch(char *s, char *sub, int subL, int R){
  this->s = s;
  this->W = subL;
  this->sub = sub;
  this->R = R;
  indices.clear();
  dfa = new int*[R];
  for(int i=0;i<R;++i){dfa[i] = new int[W];for(int j=0;j<W;++j)dfa[i][j]=0;}
 }

 ~KMPSubstringMatch(){
  for(int i=0;i<R;++i) delete[] (dfa[i]);
  delete[] dfa;
 }

 void constructDFA(){  
     int X=0;
     dfa[sub[0]][0] = 1;
     for(int i=1;i<W;++i){ 
         for(int j=0;j<R;++j){
             dfa[j][i] = dfa[j][X];
         }
         dfa[sub[i]][i] = i+1;
         X = dfa[sub[i]][X];
     }
 }

 void find(int slength, int sublen){
        int i, j;
        for(i=0, j=0;i<slength;++i){
            j=dfa[s[i]][j]; 
            if(j==W){ 
    indices.push_back(i-sublen+1); 
                j=0;
                i=(i-sublen+1);
            }
        }  
    } 
    
 static void find(char *s, char *sub, int slen, int subL){
        KMPSubstringMatch *kmp = new KMPSubstringMatch(s, sub, subL, 257); 
        kmp->constructDFA();
        kmp->find(slen, subL);
        delete kmp;
    }
};

char s[301][301];
char world[2001][2001];

int main(){
 int a, b;  
 scanf("%d %d", &a, &b);  
 for(int i=0;i<a;++i){scanf(" %s", s[i], sizeof(char)*b);}
 int x, y;
 scanf("%d %d", &x, &y); 
 for(int i=0;i<x;++i){scanf(" %s", world[i], sizeof(char)*y);}

 bool f = false; 
 for(int i=0;i<x;++i){
  int t=0;
  char *cur = world[i];
  KMPSubstringMatch::find(cur, s[t], y, b); 
  if(!indices.empty() && a>1){
   for(int z=0;z<indices.size();++z){
    int v = indices[z]; 
    bool fl = true;
    for(int i2=i, X=0;X<a;++X,++i2){
     for(int j2=v, Y=0;Y<b;++Y,++j2){
      if(s[X][Y]!=world[i2][j2]){fl=false;break;}
     }
     if(!fl)break;
    }
    if(fl){printf("(%d,%d)\n", i+1, v+1);f = true;}
   }
  }else if(!indices.empty() && a==1){
   for(int z=0;z<indices.size();++z){
    int v = indices[z];
    f = true;
    printf("(%d,%d)\n", i+1, v+1);
   }
  }
 }
 if(!f)printf("NO MATCH FOUND...\n");  
 return 0;
}

KMP (Knuth-Morris-Pratt) Substring Match - Linear Time Substring Match Algorithm - Java

KMP algorithm needs no buffer to record the data. It can be used to find the substring on-the-fly. It is a linear time algorithm. It uses a DFA to achieve linear time search. The construction of DFA takes O(R*W) time and space where R is the number of different characters used and M is the length of the pattern to be search in a text of length N.

Source:

public class KMPSubstringMatch {
    
    private int W, R;
    
    private int[][] dfa;
    private String s;
    private String sub;
    
    public KMPSubstringMatch(String s, String sub, int R){
        this.W = sub.length();
        this.R = R;
        this.sub = sub;
        this.s = s;
        dfa = new int[R][W];
    }
        
    public void constructDFA(){  
        int X=0;
        dfa[sub.charAt(0)][0] = 1;
        for(int i=1;i<W;++i){ 
            for(int j=0;j<R;++j){
                dfa[j][i] = dfa[j][X];
            }
            dfa[sub.charAt(i)][i] = i+1;
            X = dfa[sub.charAt(i)][X];
        }
    }
    
    public int find(){
        int i, j;
        for(i=0, j=0;i<s.length() && j!=W;++i){
            j=dfa[s.charAt(i)][j]; 
        }
        if(j==W)return i-sub.length();
        else return -1; 
    } 
    
    public static void find(String s, String sub){
        KMPSubstringMatch kmp = new KMPSubstringMatch(s, sub, 257);
        kmp.constructDFA();
        System.out.println("Substring \""+sub+"\" found at index "+kmp.find());
    }
    
    public static void main(String[] args){
        String s = "haystackintheneedleinthehaystack";
        
        find(s, "needle");
        find(s, "jatin");
        find(s, "ack");
        find(s, "a");
        find(s, "z");
        find(s, "lein");
    }
}

Output:

Substring "needle" found at index 13
Substring "jatin" found at index -1
Substring "ack" found at index 5
Substring "a" found at index 1
Substring "z" found at index -1
Substring "lein" found at index 17