如何使这段在矩阵中查找字符串的代码工作得更快，例如在线性时间内？

Question

在这个问题中，我必须计算矩阵中有多少张笑脸。幸福的脸代表：

:-)

。笑脸的每个字符都必须按升序排列在不同的行中，并且也必须按升序排列在不同的列中。

例如矩阵：

7 4
:-)-
\-::-
)-)-
)-::
\--))
::))
)---

答案是10。

我已经使用大量

for

循环尝试了这个解决方案。解决方案是正确的，但是太慢了。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef vector< vector<char> >Matriu;

int numberSubsequences(const Matriu &m){
int row=m.size();
int column=m[0].size();
int counter=0;


for(int i=0; i<row; ++i){
    for(int j=0; j<column; ++j){
    if(m[i][j]==':'){
        for(int i2=i+1; i2<row; ++i2){
            for(int j2=j+1; j2<column;++j2){
                if(m[i2][j2]=='-'){
                    for(int i3=i2+1; i3<row; ++i3){
                        for(int j3=j2+1; j3<column; ++j3){
                            if(m[i3][j3]==')'){
                                ++counter;
                            }
                        }
                    }
                }
            }
        }
    }
    }
}
    return counter;
    }



int main(){
    int r, c;
    while(cin >> r >> c){
        Matriu m(r,vector<char>(c));
        for(int i=0; i<r; ++i){
            for(int j=0; j<c; ++j){
                cin >> m[i][j];
            }
        }
        cout << numberSubsequences(m) << endl;
    }
}

Answer 1

首先，找到矩阵包含最后一个字符

)

的所有位置。结果是一个由 0 和 1 组成的矩阵。然后，计算该矩阵的累积和 - 对于每个位置，下方和右侧有多少个

)

字符。

计算累计和的代码：

// Accumulate along rows
for (int i = 0; i < rows; ++i)
    for (int j = columns - 2; j >= 0; --j)
        tmp_mat[i][j] += tmp_mat[i][j + 1];

// Accumulate along columns
for (int i = rows - 2; i >= 0; --i)
    for (int j = 0; j < columns; ++j)
        tmp_mat[i][j] += tmp_mat[i + 1][j];

下一步：找到矩阵包含倒数第二个字符

-

的所有位置。结果是一个由 0 和 1 组成的矩阵。将它们乘以之前找到的累积和。然后计算结果的累积和。累积和表示，对于每个位置，下面和右侧有多少个字符串

-)

。

最后一步：对第一个字符

:

执行相同的操作。你只需要在整个矩阵上计算一个总和 - 不需要在这里计算累积和，因为它已经结束了。

这些计算需要深度为 2 的嵌套循环 - 复杂度为 O(xy) 而不是 O((xy)³)。

---

示例：在以下矩阵中查找

abc

：

aaabc
ababa
bbbcc

第1步：找到

c

00001
00000
00011

第2步：行累计和，然后列累计和

11111            33332
00000    then    22221
22221            22221

第三步：找到

b

，然后乘以累计和

00010            00010
01010    then    02010
11100            00000

第四步：行累计和，然后列累计和

11110            44220
33110    then    33110
00000            00000

第五步：找到

a

，然后乘以累计和

11100            31100
10101    then    00000
00000            00000

第6步：求和

5

请注意，当乘以累积和时，我们必须采用适当索引处的元素。在下图中，我们将 X 乘以 Y。

*****    *****
*X***    *****
*****    **Y**

由于字符串的限制，元素 Y 在 X 的下方和右侧移动 1 - 字符串元素的索引应至少前进 1。如果允许我们找到在行或列中占据相邻位置的字符串，我们将矩阵的元素相乘而不进行移位。