Which algorithm to choose for searching in the text?

Question

Algorithms

Problem: The text (n lines) consists of alphabetic characters and spaces. There can be any number of consecutive spaces. If string k has 2 spaces at positions i ,i+1 and string k+1 has 2 spaces at positions i, i+1, a square of spaces is formed. Find the largest square of spaces in the given text.
An example of text, the largest square is 3 by 3 (asterisks instead of spaces):
dfem***jde*df**d
ldfg***sevxfbtbf
nmnr***wesdrtda Tell me
which algorithm to choose? I wrote an enumeration, but it is not optimal and is not the correct solution to the problem.

Answer 1

Go through the text, fill in a rectangular table - at each position, the number of spaces, starting from it.
Determine the largest potential square by the longest line of spaces.
Run a loop: for all values ​​not less than m (the current maximum), check that m - 1 following lines in the same position have values ​​not less than m.
Not found - decrease m, repeat the cycle.

Answer 2

You can write a dynamic algorithm.
For each cell we will store:
left[x][y] - the number of spaces in a row to the left of the current cell
up[x][y] - the number of spaces in a row to the top of the current cell
square[x][y] - the size of the square of spaces with the right bottom corner in current cell
Then:
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)
In this way, you can fill the entire square moving along the lines from left to right, from top to bottom.

Answer 3

You can use the "game of sea battle" algorithm:
1. There is an initial matrix with data
2. You create the same empty matrix - this will be a mask where you mark the processed cells.
3. Sequentially pass through the original matrix (taking into account the processed cells in the mask). If it's a letter, mark it in the mask. If there is a gap, you recursively go through all the connected cells (like water fills the area), while marking the cells in the main mask and the additional mask layer of the active revealed figure (from the gaps).
4. You cut the figure in the additional layer (it can be of any shape, there are two spaces in one line, five in the other) to the necessary requirements (in this case, a square) and save the result.
5. You return to point 3 if there are unprocessed cells.