時間計算量 \(O(HW^2)\) を達成できます。

部分長方形に使用される列の個数 \(w\) で場合分けし、 \(w=1,2, \ldots W\) の順に考えます。横 \(w\) マスが連続する部分は \(H(W-w+1)\) 個、また反転を含めると \(2H(W-w+1)\) 個ありますが、それらを分類して整数に置き換えます（同じ文字列には同じ整数、異なる文字列には異なる整数になるようにする）。 \(w\) が \(1\) だけ小さい場合の情報があれば、基数ソートを用いて \(O(HW)\) 時間で求められます。

部分長方形に使用される列の範囲で場合分けします。長さ \(w\) の部分文字列がすべて分類されていることにより、次の問題に帰着できます。

長さ \(H\) の数列 \(A\) , \(B\) が与えられます。 \(A _ x=B _ y\) かつ \(B _ x = A _ y\) であることを \(f(x,y)\) と表します。

\(1 \leq l \leq r \leq H\) を満たす整数の組 \((l,r)\) であって、 \(f(l+i,r-i)\) (\(0 \leq i \leq r-l\)) を満たすものの個数を求めよ。

これに対して Manacher のアルゴリズムを使います。数えるものが回文とは異なりますが、 Manacher のアルゴリズムで利用する性質「文字列 \(S\) が回文である \(\iff\) 文字列 \(S\) を逆順に読んだ文字列が回文である」はこの設定に置き換えても成り立ちます。長さ \(1\) の文字列が条件を満たさない場合が新たに表れることに注意すれば、上記の問題は計算量 \(O(H)\) で解けます。

以上により、全体の計算量は \(O(HW^2)\) になります。

プログラム例 (C++)

他にも、 suffix array 、 LCP array 、 \(O(1)\) 時間の区間最小値クエリを用いれば、 \(O(HW^2)\) 時間の方法をいくつか作れると思います。