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

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)
}

# -*-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:
        return0
    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))