#ifdef _WIN32 # define LL "%I64d" #else # define LL "%ll" #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define null NULL #define mp make_pair #define pb(a) push_back(a) #define sz(a) ((int)(a).size()) #define all(a) a.begin() , a.end() #define fi first #define se second #define relaxMin(a , b) (a) = min((a),(b)) #define relaxMax(a , b) (a) = max((a),(b)) #define SQR(a) ((a)*(a)) typedef vector vi; typedef pair pii; typedef long long ll; // BOR #define alp 26 #define HOW 1000100 #define NONE -1000000 struct node{ int next[alp] , go[alp]; int par , link; char pch; int word , up; }; node T[HOW]; int SZ; void clear(int w){ memset(T[w].next , -1 , sizeof T[w].next); memset(T[w].go , -1 , sizeof T[w].go); T[w].par = T[w].link = -1; T[w].pch = 0; T[w].word = NONE; T[w].up = NONE; } void init(){ // pered izpolzovaniem vuzuvaj clear(0); SZ=1; } void add(char* w , int id){ // Portit w int L = strlen(w) , pos=0; for(int i=0;i= 0){ if(T[vr].word != NONE) ret.pb(T[vr].word); vr = get_word(vr); } return ret; } // Solution #define MID 1005 int R , C , W; char in[1010][1010]; char wrds[1010][1010]; int _WL[1010]; map< string , pair > ans; int hor[1010] , ver[1010] , ipj[2010] , imj[2100]; void relax(const vi& on , pair data){ for(int i=0;i=0;--i) for(int j=C-1;j>=0;--j){ int I = i , J = j, IPJ = i + j , IMJ = i - j + MID; hor[I] = go(hor[I] , in[i][j] - 'A'); relax(words(hor[I]) , mp(mp(i , j) , 'G')); ver[J] = go(ver[J] , in[i][j] - 'A'); relax(words(ver[J]) , mp(mp(i , j) , 'A')); ipj[IPJ] = go(ipj[IPJ] , in[i][j] - 'A'); relax(words(ipj[IPJ]) , mp(mp(i , j) , 'B')); imj[IMJ] = go(imj[IMJ] , in[i][j] - 'A'); relax(words(imj[IMJ]) , mp(mp(i , j) , 'H')); } for(int i=0;i out = ans[string(wrds[i])]; //cout<