Какой алгоритм выбрать для поиска в тексте?

Question

[MartiMarti]

Задача: текст (n строк) состоит из букв алфавита и пробелов. Последовательных пробелов может быть любое количество. Если в строке k 2 пробела на позициях i ,i+1 и в строке k+1 2 пробела на позициях i, i+1, образуется квадрат пробелов. Найдите наибольший квадрат пробелов в данном тексте.

Пример текста, наибольший квадрат - 3 на 3 (вместо пробелов звездочки):
dfem***jde*df**d
ldfg***sevxfbtbf
nmnr***wesdrtda

Подскажите, какой алгоритм выбрать? Я написал перебор, но он не оптимальный и не является правильным решением задачи.

Answer 1

[Adamos]

Проходите текст, заполняете прямоугольную таблицу - на каждой позиции количество пробелов, начиная с нее.
Определяете наибольший потенциальный квадрат по самой длинной строчке пробелов.
Запускаете цикл: для всех значений не меньше m (текущий максимум) проверяете, чтобы в m - 1 следующих строчках на той же позиции значения были не меньше m.
Не нашлось - уменьшаем m, повторяем цикл.

Answer 2

[tsarevfs]

Можно написать динамический алгоритм.
Для каждой ячейки будем хранить:
left[x][y] - количество пробелов подряд слева от текущей ячейки
up[x][y] - количество пробелов подряд сверху от текущей ячейки
square[x][y] - размер квадрата из пробелов с правым нижним углом в текущей ячейке

Тогда:
left[x][y] = isspace(a[x][y]) ? left[x][y - 1] + 1 : 0
up[x][y] = isspace(a[x][y]) ? left[x - 1][y] + 1 : 0
square[x][y] = min(left[x][y] + 1, left[x][y] + 1, square[x - 1][y - 1] + 1)

Таким образом можно заполнить весь квадрат двигаясь по строкам слева направа, сверху вниз.

Comments

[Adamos]

Самое оптимальное решение.

Answer 3

[Dmitry Koshelenko]

Можно использовать алгоритм "игры в морской бой":
1. Есть исходная матрица с данными
2. Создаешь такую же пустую матрицу - это будет маска, где помечаешь обработанные ячейки.
3. Последовательно проходишь по исходной матрице (с учетом обработанных ячеек в маске). Если буква - помечешь в маске. Если пробел - рекурсивно проходишь по всем связанным ячейкам (как вода заливает область), помечая при этом ячейки в основной маске и дополнительном слое-маске активной выявляемой фигуры (из пробелов).
4. Обрезаешь фигуру в дополнительном слое (она может быть произвольной формы, в одной строке два пробела, в другой - пять) под необходимые требования (в данном случае - квадрат) и сохраняешь полученный результат.
5. Возвращаешься к пункту 3 если есть необработанные ячейки.