Wednesday, February 17, 2016

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

No comments:

Post a Comment