読者です 読者をやめる 読者になる 読者になる

AOJ 1316: ドーナツ

問題

The Sorcerer's Donut | Aizu Online Judge

f:id:kenkoooo:20150203190655p:plain

上のようにドーナツ状になっている文字表の中に2回出てくるフレーズを探す。2つ以上ある場合は最も長いものを返す。同じ長さなら辞書順で前にあるものを返す。

解法

例にあるとおり、

ABCD
EFGH
IJKL

のFから始めると、

FGHE
FKDEJCHIBGLA
FJB
FIDGJAHKBELC
FEHG
FALGBIHCJEDK
FBJ
FCLEBKHAJGDI

のフレーズが出来る。これらのフレーズと、その部分文字列(例えばFCLEBKHAJGDIならFCLEBKなど)をすべて記録しておき、2回めに出てきた時に拾えるようにしておく。データ大きくなってくると2回目かどうかのチェックに時間がかかるので、頭文字と文字列の長さで26*200=5200分類して高速化する。

解答コード

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        while (true) {
            int H = scan.nextInt();
            if (H == 0) {
                scan.close();
                break;
            }
            int W = scan.nextInt();

            char[][] table = new char[H][];
            for (int i = 0; i < table.length; i++) {
                // 与えられるテーブルをしまっておく
                table[i] = scan.next().toCharArray();
            }

            String answer = "";// 解答
            int[] dir = { -1, 0, 1 };// 方向

            @SuppressWarnings("unchecked")
            ArrayList<String>[][] parts = new ArrayList[26][201];// [頭文字][長さ]の文字列を格納する
            for (int i = 0; i < parts.length; i++) {
                for (int j = 0; j < parts[i].length; j++) {
                    parts[i][j] = new ArrayList<String>();
                }
            }

            for (int i = 0; i < table.length; i++) {
                for (int j = 0; j < table[i].length; j++) {
                    for (int k = 0; k < dir.length; k++) {
                        for (int l = 0; l < dir.length; l++) {
                            if (dir[k] == dir[l] && dir[k] == 0) {
                                continue;
                            }

                            int nowi = i;
                            int nowj = j;
                            StringBuilder sb = new StringBuilder();
                            sb.append(table[nowi][nowj]);

                            while (true) {
                                nowi = (nowi + dir[k] + H) % H;
                                nowj = (nowj + dir[l] + W) % W;

                                if (nowi == i && nowj == j) {
                                    // 元の場所に戻ってきてたら終わる
                                    break;
                                }

                                sb.append(table[nowi][nowj]);// 文字を後ろに付け加える

                                char init = (char) (table[i][j] - 'A');// 頭文字
                                String seq = sb.toString();// 文字列
                                int length = sb.length();// 文字列の長さ

                                if (parts[init][length].contains(seq)) {
                                    if (length > answer.length()) {
                                        answer = seq;
                                    } else if (length == answer.length()) {
                                        // 文字列の長さが同じ時は辞書順で前のやつを採用する
                                        if (answer.compareTo(seq) > 0) {
                                            answer = seq;
                                        }
                                    }
                                } else if (length >= 2) {
                                    // 2文字以上ならリストに加えておく
                                    parts[init][length].add(seq);
                                }
                            }
                        }
                    }

                }
            }
            if (answer.equals("")) {
                System.out.println(0);
            } else {
                System.out.println(answer);
            }
        }

    }
}