AOJ1316 The Sorcerer's Donut

問題リンク The Sorcerer's Donut

• 概要

H*Wに文字が並んでいる。ある文字からはじめて、周囲8方向へ向きを決めて読み続けることができる。表の外へはみ出すとき、上辺へはみ出すならば下の辺へ、右辺へはみ出すならば左辺へ、というように読み続ける。
magic spellとは、2文字以上の文字列で、2回以上出現するもののことである。ただし、始まりの文字が異なり、互いにオーバラップしていないようなものである。H*Wの表中で最も長いmagic spellを答えよ。そのようなものが複数ある場合辞書順で小さいものを答えよ。
3 <= H <= 10
3 <= W <= 20

• 解法

点i, jから向きdに読み始め、点i, jの文字を先頭とする部分文字列を全て列挙していきます。
set[i][j]はアルファベットiから始まり、長さjの文字列を蓄える文字列集合です。
部分文字列を1文字ずつ伸ばしていって、もし、それがsetに含まれていたらそれは異なる箇所でオーバラップせず出現した文字列なのでmagic spellです。これを全ての点を始点に、全方向試していきます。

• ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//The Sorcerer's Donut
public class AOJ1316 {

	@SuppressWarnings("unchecked")
	void run(){
		int[][] move = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
		Scanner sc = new Scanner(System.in);
		for(;;){
			int h = sc.nextInt(), w = sc.nextInt();
			if((h|w)==0)break;
			char[][] m = new char[h][w];
			for(int i=0;i<h;i++)m[i]=sc.next().toCharArray();
			Set<String>[][] set = new HashSet[26][201];
			for(int i=0;i<26;i++)for(int j=0;j<=200;j++)set[i][j] = new HashSet<String>();
			String res = "";
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				for(int k=0;k<8;k++){
					StringBuilder sb = new StringBuilder(m[i][j]+"");
					int pi = (i+move[k][0]+h)%h, pj = (j+move[k][1]+w)%w;
					while(pi!=i||pj!=j){
						sb.append(m[pi][pj]);
						String r = sb.toString();
						if(set[m[i][j]-'A'][r.length()].contains(r)){
							if(res.length()<r.length())res = r;
							else if(res.length()==r.length()&&r.compareTo(res)<0)res = r;
						}
						else set[m[i][j]-'A'][r.length()].add(r);
						pi = (pi+move[k][0]+h)%h; pj = (pj+move[k][1]+w)%w;
					}
				}
			}
			System.out.println("".equals(res)?"0":res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1316().run();
	}
}