Bruteforce / KMP
With bruteforce - 0.01s
With KMP - 0.17s
#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; }