python - 查找一个矩阵是否是另一个矩阵的子矩阵的有效方法？

Question

给定两个矩阵A和B。

是否有高效或更pythonic方法来查找B是否为Sub-Matrix A？

下面的代码可以工作，但是当矩阵太大时，我超出了时间限制!

注意:矩阵数据结构表示为字符串数组。

[输入]

A=[
'7283455864',
'6731158619',
'8988242643',
'3830589324',
'2229505813',
'5633845374',
'6473530293',
'7053106601',
'0834282956',
'4607924137']

B=[
'9505',
'3845',
'3530']

[代码]

def gridSearch(G, P):
    # Write your code here
    n=len(G)    # Matrix G row number
    m=len(G[0]) # Matrix G col number

    r=len(P)    # Matrix P row number
    c=len(P[0]) # Matrix P col number

    found='NO'
    for i in range(n-r+1):
        for j in range(m-c+1):
            start_row=i
            end_row=i+r
            start_col=j
            end_col=j+c
            sub=[]
            if G[start_row][start_col]==P[0][0]:
                sub=[x[start_col:end_col] for x in G[start_row:end_row] ]
            if (sub==P):
                found='YES'
                #print(i,j)
                
    return(found) 

[预期输出]

YES

Answer 1

我会利用在另一个字符串中搜索字符串的功能，而不是像您在代码中所做的那样逐个字母地搜索，如下所示:

def gridSearch(G, P):
    g_sze = len(G)
    p_sze = len(P)
    p_ptr = 0
    for g_ptr, g_row in enumerate(G):
        if P[p_ptr] in g_row:
            p_ptr += 1
            if p_ptr == p_sze:
                return True
        else:
            p_ptr = 0
            if g_sze - g_ptr < p_sze-p_ptr:
                return False

    return False

上面的代码使用了两种效率方法，首先按行搜索数组，其次当无法再匹配较小数组的剩余行时停止搜索行

鉴于您的第二个示例，这是一种使用字符串搜索方法并需要列对齐的方法。

def gridSearch2(G, P):
    g_sze = len(G)
    p_sze = len(P)
    candidates = []
    # First scan for possible start postions
    for row in range(g_sze - p_sze + 1):
        idx = 0
        while idx < g_sze - p_sze:
            ptr = G[row].find(P[0], idx)
            if ptr < 0:
                break
            candidates.append((row, ptr+idx))
            idx = idx + ptr + 1
        # test each possible start postion for matching follow on rows
        while len(candidates)  > 0:
        row, idx  = candidates.pop(0);
        rslt = True
        for pr in range(1, p_sze):
            if G[row + pr].find(P[pr], idx) != idx:
                rslt = False
                break
        if rslt:
            return True
    return False