237. Count Occurrences of a Given String in a 2D Character Array

Given an R x C grid of characters and a word, count how many times word occurs in the grid, searching only left-to-right along each row and top-to-bottom along each column (no other directions, no wraparound). Overlapping occurrences within the same row or column both count. The first line of input is R and C; the next R lines are the grid's rows; the last line is the word. Print the total count.

Input: The first line contains two integers R and C. Each of the next R lines contains a row of C characters. The final line contains the word to search for. Output: Print a single integer - the total count of occurrences found left-to-right in rows and top-to-bottom in columns.

1 <= R, C <= 100, 1 <= |word| <= 100

This problem deliberately restricts matches to only horizontal and vertical directions (no diagonals, unlike the related '8-direction word search' problem) - a crucial detail that keeps the approach simple (row/column strings) rather than needing full grid-traversal search.

In a grid of characters, count how many times a word appears reading only straight across a row (left to right) or straight down a column (top to bottom). Brute force: For every possible starting cell and direction (row or column), manually check character by character if the word matches - this is essentially the same total work as the row/column string-search approach, just organized differently; the key efficiency comes from using a proper substring-search algorithm rather than naive character comparison at every position. Optimised: Treating each row and each column as its own plain string turns this into a series of standard 1D substring-search problems (which can each be done efficiently with KMP or even a simple sliding comparison) - explicitly allowing OVERLAPPING matches within the same row or column is the one subtlety that must be handled correctly (don't skip ahead past a found match).

Precompute the word's KMP failure function once, then treat each row and each column of the grid as its own string and run the KMP string-matching algorithm along it to find every occurrence of the word, reusing the same failure function each time. KMP never re-examines a character it has already matched, so unlike the brute-force character-by-character comparison, a mismatch after a partial match doesn't force restarting from scratch, giving linear-time matching per line instead of matching-time-proportional-to-word-length per position. Time: O(R * C + (R + C) * |word|) Space: O(|word|)

Precompute the hash of the word once along with a table of powers of the hash base, then for each row and column compute a rolling hash that can be updated in O(1) per position as the window slides, comparing it against the word's hash and only falling back to an actual character comparison to rule out a rare hash collision. This reaches the same linear total scan of the grid as the KMP approach without needing to build or store a failure-function automaton, trading a small collision-handling step for a simpler, lighter-weight matching mechanism (and using a second independent hash all but eliminates false positives). Time: O(R * C + (R + C) * |word|) Space: O(1) beyond the precomputed power table

For every cell in the grid, try starting the word there and compare it character by character both going rightward along the row and downward along the column, counting a match whenever every character lines up before running off the grid. This checks every possible occurrence directly and is always correct, but comparing character by character from every single starting cell means a lot of repeated comparison work, especially when the word has internally repeated characters that cause partial matches to be re-examined. Time: O(R * C * |word|) Space: O(1)

1. Treat every row of the grid as a plain string and search it for every occurrence of the word (including overlapping matches), adding to a running total. 2. Build every column of the grid as its own string (by reading down), and search each one the same way. 3. Sum up all the matches found across every row and every column.

Time: O(R * C) for building the strings, plus O((R+C) * |word|) for searching each row and column - overall roughly proportional to the grid's size times the word's length. Space: O(R + C) if building column strings explicitly (row strings are already given), or O(1) extra if searching columns directly without building intermediate strings.

Overlapping occurrences within a single row or column, such as a repeated-character run; a word longer than both R and C (cannot occur, count 0); R, C up to 100 and word length up to 100 for performance.

Be precise about the OVERLAPPING match rule explicitly stated in the problem - a naive substring search that skips forward by the full word length after each match would under-count cases like searching for 'aa' within 'aaaa'.