一道 Google 竞赛题的解法

核心提示： typedef vector< POS > VETPOS;find中的每一个字符都有必要使用一个VETPOS类型的变量保存其在相应grid中出现的位置，这些变量的个数显然应该和find字符串的长度相等，一道 Google 竞赛题的解法(3)，假设find的长度用变量int fi

typedef vector< POS > VETPOS;

find中的每一个字符都有必要使用一个VETPOS类型的变量保存其在相应grid中出现的位置，这些变量的个数显然应该和find字符串的长度相等。假设find的长度用变量int findStrLen表示，则findStrLen = find.length()。这些VETPOS类型的变量的处理和计算的过程大多相同，显然可以使用数组来集中处理。但由于每次调用的find字符串的长度未必都相等，所以这些VETPOS类型的变量同样保存到向量(vector)中更合适。代码中我是这样定义的：

int findStrLen = find.length();
vector < VETPOS > vec(findStrLen);

这样保存find第k个字符在grid中出现位置的向量可以用vec[k]表示了。

1.2　算法

数据结构至此定义的差不多了，接着就该考虑如何遍历grid的每一个字母，并将在find中出现的字符的位置保存到相应的位置向量中去。

1.2.1

在grid中其第i个字符串可以用grid[i]表示；而在string中其第几个字符可以用成员函数at(),或者重载运算符[]取得，如find的第i个字符可以用find.at(i)或者find[i]来获得。所以在grid中取得位置为(0,1)的字符可以用表达式grid[1][0]或者grid[1].at(0)取得。要遍历grid的每一个字母，首先要知道grid中字符串的个数，这可以调用vector的size成员函数取得，假设grid中的字符串个数为int gridSize,则gridSize=grid.size()；而字符串的长度可以用string的成员函数length()取得，由于题中明确告诉我们，grid中的每个字符长度相等，所以我们只要计算其中任意一个字符串长度即可。假设grid中的每个字符长度为int gridStrLen，则gridStrLen = grid[0].length()。知道了grid中每个字符串的字符个数和总的字符串个数，我们就可以用2个嵌套的for循环遍历其中的每一个字符,代码如下：