2025-10-15：统计水平子串和垂直子串重叠格子的数目。用go语言，给定一个 m×n 的字符矩阵 grid 和一个字符串 pattern。

我们把从某个位置出发按行从左向右连续取的字符序列称为“横向连续串”：若取到行尾，会接着从下一行的开头继续取，但不会在到达最后一行后回绕到第一行。

类似地，把按列从上到下连续取的字符序列称为“纵向连续串”：若取到列底，会转到下一列的顶部继续，但不会从最后一列回到第一列。

现在统计矩阵中满足以下两个条件的格子个数：该格至少出现在一个与 pattern 完全相同的横向连续串中，同时也至少出现在一个与 pattern 完全相同的纵向连续串中。

返回这样的格子总数。

m == grid.length。

n == grid[i].length。

1 <= m, n <= 1000。

1 <= m * n <= 100000。

1 <= pattern.length <= m * n。

grid 和 pattern 仅由小写英文字母组成。

输入： grid = [[“c”,“a”,“a”,“a”],[“a”,“a”,“b”,“a”],[“b”,“b”,“a”,“a”],[“a”,“a”,“b”,“a”]], pattern = “aba”。

输出： 4。

解释：

上述被标记的单元格都同时属于至少一个 “aba” 的水平和垂直子串。

题目来自力扣3529。

1. 总体思路

1. 将二维矩阵转化为两个一维数组：

   • 水平文本 hText：按行优先顺序，把整个矩阵的所有字符拼接成一个一维数组（长度 m*n）。
   • 垂直文本 vText：按列优先顺序，把整个矩阵的所有字符拼接成一个一维数组（长度 m*n），即先取第 0 列的所有行，再取第 1 列的所有行，依此类推。

2. KMP 预计算：

   • 对 pattern 计算前缀函数（pi 数组），用于 KMP 匹配。

3. KMP 搜索标记：

   • 对 hText 进行 KMP 搜索，当发现匹配时，标记匹配的起始位置到结束位置之间的所有格子（在 hText 中对应索引范围）为“在某个水平匹配中出现过”。
   • 这里使用差分数组技巧来高效标记区间，最后通过前缀和得到每个位置是否被水平匹配覆盖。
   • 同理对 vText 做同样的处理，得到每个位置是否被垂直匹配覆盖。

4. 坐标映射与统计：

   • 水平文本的索引 idxH 对应矩阵位置 (idxH / n, idxH % n)。
   • 垂直文本的索引 idxV 对应矩阵位置 (idxV % m, idxV / m)（因为垂直文本是按列优先存储的）。
   • 我们需要判断矩阵中同一个格子 (i, j) 是否在 inPatternH 和 inPatternV 中都被标记。
   • 具体地，(i, j) 在 hText 中的索引是 i*n + j，在 vText 中的索引是 j*m + i。
   • 代码中通过 i%n*m + i/n 来映射，是因为它把 hText 的索引 i 映射到 vText 的对应格子的索引（这里 i 是 inPatternH 的索引，即 hText 的索引）。

2. 详细步骤

2.1 构建水平文本和垂直文本

• 水平文本 hText：直接按行遍历 grid，把每个字符按顺序放入一个长度为 m*n 的数组。
• 垂直文本 vText：先遍历列 j（0 到 n-1），再遍历行 i（0 到 m-1），把 grid[i][j] 依次加入数组。

2.2 计算前缀函数 pi

• 对 pattern 使用标准的 KMP 前缀函数算法，得到 pi 数组，用于在匹配失败时回退。

2.3 水平匹配标记

• 用 KMP 在 hText 中搜索 pattern。
• 当匹配成功时（match == len(pattern)），匹配覆盖的区间是 [start, start+len-1]，其中 start = i - len(pattern) + 1（这里的 i 是 hText 的当前索引）。
• 使用差分数组 diffH（长度 m*n+1），在 start 处加 1，在 start+len(pattern) 处减 1。
• 匹配完成后，对差分数组做前缀和，得到 inPatternH 数组，inPatternH[idx] > 0 表示 hText[idx] 这个位置被至少一个水平匹配覆盖。

2.4 垂直匹配标记

• 对 vText 做同样的 KMP 搜索与差分标记，得到 inPatternV 数组。

2.5 统计重叠格子

• 遍历 hText 的每个索引 idxH（0 到 m*n-1）：
  • 如果 inPatternH[idxH] > 0 且 inPatternV[idxV] > 0，其中 idxV 是同一格子在 vText 中的索引，则计数加 1。
  • 矩阵位置 (i, j) 与 idxH 的关系：i = idxH / n, j = idxH % n。
  • 该位置在 vText 中的索引是 j * m + i。
  • 代码中 idxV = i%n*m + i/n 实际上等价于 j*m + i，因为 i%n 就是 j（当 i 是 hText 索引时，i/n 是行号，i%n 是列号，但这里 i 是 idxH，所以 i/n 是行，i%n 是列，所以 i%n*m + i/n 就是 j*m + i）。

3. 复杂度分析

3.1 时间复杂度

• 构建 hText 和 vText：O(m*n)。
• 计算 pi 数组：O(L)，L 为 pattern 长度。
• KMP 搜索 hText（长度 mn）：O(mn)。
• KMP 搜索 vText（长度 mn）：O(mn)。
• 差分数组前缀和：O(m*n)。
• 最后统计：O(m*n)。

总时间复杂度：O(mn + L)，因为 mn ≥ L 可能，所以可简化为 O(m*n)。

3.2 额外空间复杂度

• hText：O(m*n)。
• vText：O(m*n)。
• pi 数组：O(L)。
• 两个差分数组：O(m*n)。

总额外空间复杂度：O(m*n)。

这样，我们就用 KMP + 差分标记 + 坐标映射的方法高效地统计了满足条件的格子数目。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

func calcPi(pattern string) []int {
	pi := make([]int, len(pattern))
	match := 0
	for i := 1; i < len(pi); i++ {
		b := pattern[i]
		for match > 0 && pattern[match] != b {
			match = pi[match-1]
		}
		if pattern[match] == b {
			match++
		}
		pi[i] = match
	}
	return pi
}

func kmpSearch(text []byte, pattern string, pi []int) []int {
	n := len(text)
	diff := make([]int, n+1)
	match := 0
	for i, b := range text {
		for match > 0 && pattern[match] != b {
			match = pi[match-1]
		}
		if pattern[match] == b {
			match++
		}
		if match == len(pi) {
			diff[i-len(pi)+1]++
			diff[i+1]--
			match = pi[match-1]
		}
	}
	for i := 1; i < n; i++ {
		diff[i] += diff[i-1]
	}
	return diff[:n]
}

func countCells(grid [][]byte, pattern string) (ans int) {
	m, n := len(grid), len(grid[0])
	hText := slices.Concat(grid...)
	vText := make([]byte, 0, m*n)
	for j := range n {
		for _, row := range grid {
			vText = append(vText, row[j])
		}
	}

	pi := calcPi(pattern)
	inPatternH := kmpSearch(hText, pattern, pi)
	inPatternV := kmpSearch(vText, pattern, pi)

	for i, x := range inPatternH {
		if x > 0 && inPatternV[i%n*m+i/n] > 0 {
			ans++
		}
	}
	return
}

func main() {
	grid := [][]byte{{'c', 'a', 'a', 'a'}, {'a', 'a', 'b', 'a'}, {'b', 'b', 'a', 'a'}, {'a', 'a', 'b', 'a'}}
	pattern := "aba"
	result := countCells(grid, pattern)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def calc_pi(pattern: str) -> list:
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[j] != pattern[i]:
            j = pi[j - 1]
        if pattern[j] == pattern[i]:
            j += 1
        pi[i] = j
    return pi

def kmp_search(text: str, pattern: str, pi: list) -> list:
    n = len(text)
    L = len(pattern)
    diff = [0] * (n + 1)  # 差分数组，最后会前缀和得到每个位置的覆盖次数
    j = 0
    for i, ch in enumerate(text):
        while j > 0 and pattern[j] != ch:
            j = pi[j - 1]
        if pattern[j] == ch:
            j += 1
        if j == L:
            start = i - L + 1
            diff[start] += 1
            diff[i + 1] -= 1
            j = pi[j - 1]
    # 前缀和还原每个位置的覆盖次数
    for i in range(1, n):
        diff[i] += diff[i - 1]
    return diff[:n]

def count_cells(grid: list, pattern: str) -> int:
    if not grid or not grid[0] or not pattern:
        return 0
    m, n = len(grid), len(grid[0])

    # 横向文本：按行从左到右拼接
    h_text = ''.join(''.join(row) for row in grid)

    # 纵向文本：按列从上到下拼接（每列从上到下然后下一列）
    v_chars = []
    for c in range(n):
        for r in range(m):
            v_chars.append(grid[r][c])
    v_text = ''.join(v_chars)

    pi = calc_pi(pattern)
    in_h = kmp_search(h_text, pattern, pi)
    in_v = kmp_search(v_text, pattern, pi)

    ans = 0
    total = m * n
    for i in range(total):
        if in_h[i] > 0:
            r = i // n
            c = i % n
            v_index = c * m + r
            if in_v[v_index] > 0:
                ans += 1
    return ans

if __name__ == "__main__":
    grid = [
        ['c', 'a', 'a', 'a'],
        ['a', 'a', 'b', 'a'],
        ['b', 'b', 'a', 'a'],
        ['a', 'a', 'b', 'a']
    ]
    pattern = "aba"
    print(count_cells(grid, pattern))