Vì $n,m$ nhỏ, ta có thể quay lui tất cả trường hợp

Ta chỉ cần quan tâm xâu tương ứng với cột thứ nhất là xâu đối xứng. Hay nói cách khác, ta chỉ cần quan tâm ký tự đầu tiên trong hàng thứ $i$ có bằng với ký tự đầu tiên trong hàng $n-i+1$ hay không. Cùng với điều kiện là các bảng phân biệt, ta có ý tưởng như sau:

• Gọi $cnt[i][j]$ là số cách xoay hàng thứ $i$ tạo ra xâu khác nhau sao cho tạo ra được ký tự $j$. Để đếm số cách xoay khác nhau, ta sử dụng hash để so sánh bằng cách sắp xếp các hash rồi so sánh với nhau.
• Sau đó ta đếm số cách thỏa mãn có thể xoay sao cho ký tự thứ nhất trong hàng $i$ bằng ký tự thứ nhất trong hàng $n-i+1$. Ta kiểm tra tất cả ký tự sau đó nhân các giá trị $cnt[i][j]$ và $cnt[n-i+1][j]$ với nhau. Riêng trường hợp $i=n-i+1$ thì ta chỉ cần đếm, không cần nhân lên.
• Cuối cùng nhân số cách tạo ra các cặp ký tự bằng nhau tương ứng.

Độ phức tạp: $O(n\times m\times log(m))$

Nhận xét: Chú ý rằng xâu kí tự ở mỗi hàng có thể được tạo từ một xâu con nhỏ hơn (tức là xâu $S_i$ có thể được tạo bằng cách ghép nhiều xâu $s$ nhỏ hơn lại). Ví dụ như xâu ababab là 3 xâu ab ghép lại với nhau. Ta dễ dàng nhận thấy chỉ cần xoay 2 lần là ababab và bababa. Từ đó ta quay về tìm xâu $s$ nhỏ nhất sao cho ghép xâu $s$ nhiều lần có thể tạo ra xâu $s_i$. Cải tiến bằng KMP.

Độ phức tạp: $O(n\times m)$