猫でもわかるWeb開発・プログラミング猫でもわかるWeb開発・プログラミング本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。初心者にとっては実装量が多めだが、難しい問題になってくると、これくらいの実装量は大したことがない。平面の探索や文字列操作など、よく出るアルゴリズムが多く含まれているため、勉強になる問題だと思う。問題文概訳あなたのマスターは1日だけ街に出かけていった。これにより、今日だけは彼に怒られずにすむ、とあなたは非常に気楽だった。マスターはあなたに、夕方までにドーナツを作っておくように注文した。ドーナッツが好きすぎて、マスターは一日に10個のドーナッツを食べる。こんな気楽な日に何故こんな雑用をしなければならないのか。先週、あなたはマスターが使う魔法について立ち聞きした。それを試そうと思った。あなたはキッチンで箒に向かって魔法を唱えた。閃光が発せられ、箒に手足が生えた。あなたは箒に、小麦粉をわたして生地をこねさせた。その早いこと早いこと。数分後、キッチンのテーブルには大量の生地が積み上げられた。これは来週一週間分のドーナツを作るのに十分な量だ。「やめていいぞ」とあなたは言ったが、箒は止まらなかった。あなたはどうやって魔法を止めるのかわからなかった。キッチンは数百のドーナツ生地でいっぱいになった。箒はまだ生地を作り続けている。箒を止めなければ、キッチンがドーナツ生地だらけになってしまう。あなたはマスターの書斎に行き、魔法の止め方が書いてあるノートを発見した。それで終わりではなかった。ノートに書いてあった魔法は簡単には読めなかった。魔法を読むにはドーナツ型のプラスチックが必要だった。そこに文字を書き込んだ(図B.2のように)。マスターは意味がわからないようにそこに呪文を隠していた。あなたは、その中に呪文が2回以上登場していることを知っていた。呪文は必ずしも左から右に書かれているとは限らない。8方向(上下左右と斜め)のいずれかの方向に書かれている。呪文は、1回以上出現する最も長い文字列である。プラスチックの正面には正方形が書かれており、その正方形1つに文字が1つ書かれている。文字は正方形の列である。その正方形列は以下の条件を持つ。(違う正方形列が同じ正方形を使うことはありえる)開始地点が異なるか、開始地点からの進む方向が異なる場合、異なる正方形列とみなされる。「回文」はこの条件を満たすので、2つの文字列とみなされることに注意せよ。ドーナッツに書かれた文字は以下のような行列で与えられるABCDEFGHIJKLドーナツの表面は終わりがないことに注意せよ。右と左はつながっている。そのため、行列の縦や横よりも長い文字列ができることもある。FGHEFKDEJCHIBGLA...のような文字列も上のドーナツに含まれる文字列である。これはドーナツのパターンのサイズである。続くh行にw文字の文字れつが入力される。文字列は大文字のA-Zからなる。入力の終わりは2つのゼロで表される。出力それぞれのデータセットに対して、呪文を出力せよ。最長の文字列が複数あった場合、辞書順で一番前のものを出力せよ。スペルは2文字以上であると知られている。スペルが見つからなかった場合、0を出力せよ。するが、インデックスがマイナスの方向に飛び出すときにバグらないよう注意すでにsetに入っていた場合は2回目の出現であるこのとき、この文字列が最長なら長さと単語を記憶しておく長さが同じなら辞書順最小のものである。スポンサーをお願いしますブログを投稿したらX(twitter)でお知らせしています。