s,n,u,k,e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所の条件のうち最初の \(1\) つを除いた条件、すなわち

• \(1\leq i\leq 4\) について、\(C_i\) と \(C_{i+1}\) は頂点または辺を共有している。
• \(C_1,C_2,C_3,C_4,C_5\) の中心はこの順に一直線上に等間隔で並んでいる。

をみたす \(5\) つのマスの組 \((C_1,C_2,C_3,C_4,C_5)\) を良い組 とよぶことにします。

\(C_1\) と \(C_2\) を定めた時、 \((C_1,C_2,C_3,C_4,C_5)\) が良い組となるような、\(C_3,C_4,C_5\) の候補は存在すれば一意に定まります。 具体的には、上から \(i\) 行目かつ左から \(j\) 列目のマスを \((i,j)\) で表し、\(C_1=(x_1,y_1)\), \(C_2=(x_2,y_2)\) とすると、 \((C_1,C_2,C_3,C_4,C_5)\) が良い組となるようにするためには、\(i=3,4,5\) に対して \(C_i=(x_1+(i-1)(x_2-x_1),y_1+(i-1)(y_2-y_1))\) とする他ありません。このようなマスがとれない可能性もあり、その場合は\(C_1\) と \(C_2\) に対応する良い組がないという事になります。 さて、\(C_1,C_2\) は少なくとも頂点を共有している必要があるため、\(C_1\) を定めた時、\(C_2\) としてあり得るのは高々 \(8\) つとなります。よって、マス目の中に存在する良い組は高々 \(8HW\) 個しかなく、s,n,u,k,e が この順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所はこのうちのいずれかであるため、良い組全てについて問題文の \(1\) つめの条件 (\(C_1,C_2,C_3,C_4,C_5\) に書き込まれた英小文字はそれぞれ s,n,u,k,e である事) をみたすかチェックすれば良いです。見なければならないマスはのべ高々 \(40HW(\leq 4\times10^5)\) 個となるため、時間的にも十分間に合います。

よって、この問題を解く事ができました。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,m,x,y;
	int dx[8]={-1,-1,-1,0,0,1,1,1};
	int dy[8]={-1,0,1,-1,1,-1,0,1};
	string str;

	cin>>n>>m;
	vector<string> s(n);
	for(int i=0;i<n;i++)cin>>s[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int k=0;k<8;k++){
				str="";
				for(int t=0;t<5;t++){
					x=i+t*dx[k],y=j+t*dy[k];
					if((x<0)||(x>=n)||(y<0)||(y>=m))break;
					str+=s[x][y];
				}
              	if(str=="snuke"){
					for(int t=0;t<5;t++){
						x=i+t*dx[k]+1,y=j+t*dy[k]+1;
						cout<<x<<" "<<y<<endl;
					}
					return 0;
				}
			}
		}
	}

	return 0;
}