Count Cells in Overlapping Horizontal and Vertical Substrings

medium string matching matrix KMP

Problem

Given an m × n grid of lowercase letters and a string pattern. A horizontal substring reads cells row by row, left to right (wrapping to the next row's first column, never from the bottom row back to the top). A vertical substring reads cells column by column, top to bottom (wrapping to the next column's first row, never from the last column back to the first).

Count the cells that are part of at least one horizontal occurrence of pattern and at least one vertical occurrence of pattern.

Inputgrid = [[a,a,c,c],[b,b,b,c],[a,a,b,a],[c,a,a,c],[a,a,b,a]], pattern = "abaca"

Output1

"abaca" appears once read horizontally and once read vertically; the two occurrences share exactly one grid cell.

grid (rows separated by ; , cells by ,)

pattern

def countCells(grid, pattern):
    m, n, p = len(grid), len(grid[0]), len(pattern)
    total = m * n

    # KMP: return every start index of pattern inside text.
    def search(text):
        fail = [0] * p
        k = 0
        for i in range(1, p):
            while k and pattern[i] != pattern[k]:
                k = fail[k - 1]
            if pattern[i] == pattern[k]:
                k += 1
            fail[i] = k
        starts, k = [], 0
        for i in range(len(text)):
            while k and text[i] != pattern[k]:
                k = fail[k - 1]
            if text[i] == pattern[k]:
                k += 1
            if k == p:
                starts.append(i - p + 1)
                k = fail[k - 1]
        return starts

    # Row-major reading: index t -> cell (t // n, t % n).
    h_text = [grid[t // n][t % n] for t in range(total)]
    # Column-major reading: index t -> cell (t % m, t // m).
    v_text = [grid[t % m][t // m] for t in range(total)]

    horiz = [[False] * n for _ in range(m)]
    for s in search(h_text):
        for t in range(s, s + p):
            horiz[t // n][t % n] = True

    count = 0
    for s in search(v_text):
        for t in range(s, s + p):
            r, c = t % m, t // m
            if horiz[r][c]:          # in both a horizontal and vertical match
                count += 1
    return count

function countCells(grid, pattern) {
  const m = grid.length, n = grid[0].length, p = pattern.length;
  const total = m * n;

  // KMP: return every start index of pattern inside text.
  function search(text) {
    const fail = new Array(p).fill(0);
    let k = 0;
    for (let i = 1; i < p; i++) {
      while (k && pattern[i] !== pattern[k]) k = fail[k - 1];
      if (pattern[i] === pattern[k]) k++;
      fail[i] = k;
    }
    const starts = []; k = 0;
    for (let i = 0; i < text.length; i++) {
      while (k && text[i] !== pattern[k]) k = fail[k - 1];
      if (text[i] === pattern[k]) k++;
      if (k === p) { starts.push(i - p + 1); k = fail[k - 1]; }
    }
    return starts;
  }

  // Row-major reading: index t -> cell (t / n, t % n).
  const hText = [], vText = [];
  for (let t = 0; t < total; t++) hText.push(grid[(t / n) | 0][t % n]);
  for (let t = 0; t < total; t++) vText.push(grid[t % m][(t / m) | 0]);

  const horiz = Array.from({ length: m }, () => new Array(n).fill(false));
  for (const s of search(hText))
    for (let t = s; t < s + p; t++) horiz[(t / n) | 0][t % n] = true;

  let count = 0;
  for (const s of search(vText))
    for (let t = s; t < s + p; t++) {
      const r = t % m, c = (t / m) | 0;
      if (horiz[r][c]) count++;        // in both a horizontal and vertical match
    }
  return count;
}

int countCells(char[][] grid, String pattern) {
    int m = grid.length, n = grid[0].length, p = pattern.length();
    int total = m * n;
    char[] hText = new char[total], vText = new char[total];
    for (int t = 0; t < total; t++) hText[t] = grid[t / n][t % n];
    for (int t = 0; t < total; t++) vText[t] = grid[t % m][t / m];

    boolean[][] horiz = new boolean[m][n];
    for (int s : search(hText, pattern))
        for (int t = s; t < s + p; t++) horiz[t / n][t % n] = true;

    int count = 0;
    for (int s : search(vText, pattern))
        for (int t = s; t < s + p; t++) {
            int r = t % m, c = t / m;
            if (horiz[r][c]) count++;        // in both directions
        }
    return count;
}

// KMP: return every start index of pattern inside text.
List<Integer> search(char[] text, String pat) {
    int p = pat.length();
    int[] fail = new int[p];
    int k = 0;
    for (int i = 1; i < p; i++) {
        while (k > 0 && pat.charAt(i) != pat.charAt(k)) k = fail[k - 1];
        if (pat.charAt(i) == pat.charAt(k)) k++;
        fail[i] = k;
    }
    List<Integer> starts = new ArrayList<>();
    k = 0;
    for (int i = 0; i < text.length; i++) {
        while (k > 0 && text[i] != pat.charAt(k)) k = fail[k - 1];
        if (text[i] == pat.charAt(k)) k++;
        if (k == p) { starts.add(i - p + 1); k = fail[k - 1]; }
    }
    return starts;
}

vector<int> search(const string& text, const string& pat) {
    int p = pat.size();
    vector<int> fail(p, 0), starts;
    int k = 0;
    for (int i = 1; i < p; i++) {
        while (k && pat[i] != pat[k]) k = fail[k - 1];
        if (pat[i] == pat[k]) k++;
        fail[i] = k;
    }
    k = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        while (k && text[i] != pat[k]) k = fail[k - 1];
        if (text[i] == pat[k]) k++;
        if (k == p) { starts.push_back(i - p + 1); k = fail[k - 1]; }
    }
    return starts;
}

int countCells(vector<vector<char>>& grid, string pattern) {
    int m = grid.size(), n = grid[0].size(), p = pattern.size();
    int total = m * n;
    string hText(total, ' '), vText(total, ' ');
    for (int t = 0; t < total; t++) hText[t] = grid[t / n][t % n];
    for (int t = 0; t < total; t++) vText[t] = grid[t % m][t / m];

    vector<vector<bool>> horiz(m, vector<bool>(n, false));
    for (int s : search(hText, pattern))
        for (int t = s; t < s + p; t++) horiz[t / n][t % n] = true;

    int count = 0;
    for (int s : search(vText, pattern))
        for (int t = s; t < s + p; t++) {
            int r = t % m, c = t / m;
            if (horiz[r][c]) count++;        // in both directions
        }
    return count;
}

Explanation

The grid can be read as two long strings. The horizontal string is simply the rows concatenated left to right, so cell (r, c) sits at index r·n + c. The vertical string is the columns concatenated top to bottom, so cell (r, c) sits at index c·m + r. Both strings have length m·n.

Because the wrap rule for each direction is exactly "spill into the next row / column," a substring that equals pattern is nothing more than an ordinary occurrence of pattern inside the corresponding linear string. So we run a linear-time substring search — KMP — once on the horizontal string and once on the vertical string.

Each match covers p = pattern.length consecutive indices. We translate those indices back to grid cells (using the index formulas above) and mark them. A boolean grid horiz records every cell touched by a horizontal match.

Then we sweep the vertical matches. For each cell a vertical match covers, we check horiz[r][c]; if it is already set, this cell lies in both a horizontal and a vertical occurrence of the pattern, so we count it. That intersection of the two coverage sets is the answer.

For Example 1 with pattern = "abaca" there is one horizontal match and one vertical match, and they overlap in a single cell, giving the answer 1.

Time: O(m·n) Space: O(m·n)