問題URL
注 : この解法は公式解説に書かれている解ではありません
愚直解
ある $A,B$ について、 $2$ つ目の盤面がよい盤面かどうかを判定するには比較する文字が $N^2$ 個あるので $O(N^2)$ 回の比較をしなければいけません。
また、 $A, B$ の選び方は $N^2$ 通りあるので、総計算量は $O(N^4)$ になり、TLEします。
高速化
$X_{i,j}=S_{i,j}S_{i,j+1}S_{i,j+2}...S_{i,j+N-1}, Y_{i,j}=S_{i,j}S_{i+1,j}S_{i+2,j}...S_{i+N-1,j}$ とします。ただし添え字は全て1-indexedです。
(直感的に言うと、 $X_{i,j}$ はマス $(i,j)$ から右に、 $Y_{i,j}$ はマス $(i,j)$ から下に読んでいった文字列)
この時、ある $A, B$ の選び方について $2$ つ目の盤面がよい盤面であるということは、
$X_{A+1, B+1}＝Y_{A+1, B+1}$
$X_{A+2, B+1}＝Y_{A+1, B+2}$
$X_{A+3, B+1}＝Y_{A+1, B+3}$
:
$X_{A+2, B+N}＝Y_{A+1, B+N}$
であることと同じです。これを素直に比較していては総計算量は $O(N^4)$ で変わりません。
しかし、あらかじめ $X_{i,j}$ と $Y_{i,j}$ に何らかのhash関数を用いてhash値を求めておけば、文字列の比較にかかる計算量が $O(1)$ となり、総計算量は $O(N^3)$ に落とすことができます。