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

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

Можно написать динамический алгоритм.
Для каждой ячейки будем хранить:
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)

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

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