Будем для удобства называть слова top, bottom, left, right — соответственно верхнее слово, нижнее, левое и правое в расположении.
Для начала переберем, какое слово является top, какое bottom и т.д. (таких вариантов ровно 4! = 24 штуки). После этого посчитаем, сколько из фиксированных top, bottom, left и right можно составить кроссвордов:
- Переберем, где left, right пересекают top — O(|w|2);
- Переберем сдвиг bottom относительно top — O(|w|);
- Переберем расстояние между top, bottom — O(|w|);
- Теперь осталось понять, сколькими различными способами можно подвигать left, right, чтобы символы на пересечении совпали с символами из top и bottom;
- Двигать left, right можно независимо, поэтому посчитаем для каждой отдельно, а потом перемножим;
- Подсчет для каждой отдельно — O(|w|);
- Итого получаем асимптотика O(|w|5), что на самом деле является довольно большой оценкой сверху и спокойно укладывается в TL.
Также можно было соптимизировать это решение до более хорошей асимптотики, но этого в задаче не требовалось.