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

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

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

Efficient way to find if a Matrix is Sub-Matrix of another one?

python

matrix

np