問題1 - 問題2 - 問題3 - 問題4 - 問題5 - 問題6
NPCA(Nanohana Perfect Classic magical Academy) に通う少年hiromuは、「Andvoid式」と「jOS式」のどちらの魔法女装少年になろうか悩んでいる。
そこで、双方の違いを探るために「Andvoid式」の魔法の使い手 Mine と「jOS式」の魔法の使い手 Tehu に魔法陣を見せてもらい、類似度を調べることにした。
双方の魔方陣は N 文字の大文字アルファベット(A~Z) が同一円周上に等間隔で並んだ形をしている。
ここで「類似度」を定義する。
魔方陣を重ね合わせてみて同じ位置に同じ文字があるような箇所の個数をXとする。
双方の魔方陣を回転させると X は変化するが、これの最大値を類似度とする。
例えば、図1(Sample input 1に対応している)では、上側の "B" のみが一致しているので、X は 1 である。
図2のように、両方の魔法陣を上側が "A" になるように回転させると、上側の "A" と右側の "B" が一致しているので、X は 2 となりこれは最大なので、これらの魔法陣の類似度は 2 である。
しかし Mine・Tehuの魔法陣は大きく、手作業で類似度を調べるのは困難である。
そこで、少年hiromuはプログラマであるあなたに助けを求めた。
1行目に 魔法陣を構成する文字の数 N が、
2行目に「Andvoid式」の魔法陣を構成する文字列が、
3行目に「jOS式」の魔法陣を構成する文字列が書かれている。
「Andvoid式」の魔法陣と「jOS式」の魔法陣の類似度の最大値を1行に出力せよ。
1 ≦ N ≦ 1,000
ーSample input 1ー
3
BAB
BCA
ーSample output 1ー
2
ーSample input 2ー
9
MIDCHILDA
BELKASIKI
ーSample output 2ー
3