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