Aho-Corasick で 2 次元パターンマッチング

これは IQ が 1 Advent Calendar の 21 日目の記事です。

adventar.org

20 日目は 

k3ntaroo.hatenablog.com

 

Aho-Corasick とは

chakku.hatenablog.com

この Aho-Corasick を使って 2 次元の文字列の中からパターンを探す方法を書く。

やり方

下にあるテキスト T からパターン P を検索する場合を例に説明する。

f:id:tobya:20171220213627p:plain

パターン P を行単位で区切り、 Aho-Corasick を使ってパターンマッチングオートマトンを構築する。そうすると下の図のようなオートマトンができる。さらにこのオートマトンの、各行の文字列を受理する状態番号を覚えておく。

f:id:tobya:20171220213712p:plain

次にテキスト T を行単位で区切り、オートマトンに流し込む。この時に状態遷移の番号を新しいテキスト T' として覚えておく。

f:id:tobya:20171220213728p:plain

この T' をよく見ると T の中でパターンが現れる箇所の一番右の列の箇所が最初に覚えておいたパターンの受理状態の番号になっているので、KMP とかで探す。

f:id:tobya:20171220213758p:plain

Pattern Search | Aizu Online Judge で試せる。

実装

参考文献

THE SUSHI-WARE LICENSE の紹介

この記事は Aizu Advent Calendar 2017 - Adventar の 17 日目の記事です。

前日 ESP8266を使ってIotをするための準備を一から始める. - バグだらけ会津若松

 

The SUSHI-WARE LICENSE とは

github.com

@make_now_just さんが作ったライセンスで、一言で言うと

「このライセンスが付いているものを使用したら、今度自分に寿司を奢ってください」

と言う内容のライセンスです。

 

会津のおすすめ寿司屋

tabelog.com

寿し和 - 七日町/寿司 [食べログ]

良い。

まとめ

良い。

 

 

 

転職して2ヶ月が経った

転職して2ヶ月が経った。一度ポエムを書いてみたいと思っていたので、私が退職に至るまでの過程を雑に書いておくことにした。


2016/04 ~ 2016/07
就職して研修を受けていた。職種に関わらず全員が同じ研修だったので色々な人と接することができて為になったと思う。

休み時間に休むな!と怒鳴られている同期を見て、会社に不信感を持ち始めた。


2016/08
1年間の長いエンジニア研修が始まった。受講者は4人だった。

このうち2人はプログラミング未経験で、研修内容もプログラミング未経験者を想定していた。自分にもわからないところはあるかもしれないと思い、黙って研修を受けた。
研修内容はC#だ。研修が終わったらC#を書くことになっている。


2016/09
この研修は自分には意味がないと思った。
部長にも何度か柔軟な対応を求めたが、我慢しろの一点張りだった。


2016/10 ~ 2017/01
研修を受けていたが、よく覚えていない。

この頃から酷い耳鳴りがし始めた。
受講者のうち1人が会社に来なくなった。


2017/03
長い研修が終わった。
この辺りは研修の終わりと業務の始まりでドタバタしていた為、詳細には覚えていない。


2017/04
Visual Basicを書くことになった。研修内容と業務内容が大きく食い違っていて、どうしようもなく腹が立った。

黙っていたが、すぐにVBを書いていることがバレてしまった。VB先輩という名前がついた。

転職活動をしていた先輩の、彼が転職エージェントからもらっていた企業のリストを見せてもらった。一社だけ、ずっと前から気になっていた会社があって、そこだけ受けてみることにした。


2017/05
なぜか面接官にツイッターのアカウントがバレていた。
目の前が真っ暗になった。


2017/06
内定が降ってきた。退職した。

退職時に
・若いくせに給与を気にするの?
・そんなんじゃどこでもやっていけないよ?
VBやめるって言ったら残ってくれる?
とか言っていたが、全てがどうでもよくなっていて全く聞いてなかった。全部頷いた気がする。


2017/07
VB無職と呼ばれていたようだが、インクを撒くのに忙しかった為よく覚えていない。


2017/08
無職期間が終わってしまった。


よかったこ
・堅い企業の空気がわかった。
・転職の経験が積めた。
・ちゃんとした形で退職できた。突然来なくなる人もいた。
・内定前に辞めなくてよかった。内定無くても退職するつもりではあったが。
・親しい元同期が何人かできた。
・無職期間をスプラトゥーン2の発売に重ねることができた。


反省点
・一年間の研修が確定した時点で退職するべきだった。
・転職エージェントではなくツイッター等を活用すべきだった。