我有一个网站的问题。给定一个string sand st，我必须找到 in 的所有可能st组合s。例如，
s = "doomdogged"
st = "dg"
answer = 4
我可以从 0 或 4 中选择 d，从 6 或 7 中选择 g。这给了我 4 种可能的组合。
这是我的代码：
#include <iostream>
#include <vector>
using namespace std;
string s, st;
bool target[26];
vector<int> positions[26];
vector<vector<int>> possibleCombinations;
void DFS_Enumeration(int, vector<int>*);
int DFS_index_max = 0;
int main(int argc, char *argv[])
{
int answer = 0;
cin >> s; //Given a string s
cin >> st; //Given a string st
//Find all possible combination of st in s
for ( int i = 0 ; i < 26 ; ++ i )
target[i] = 0;
for ( int i = 0 ; i < st.length() ; ++ i )
target[st[i] - 97] = 1;
for ( int i = 0 ; i < 26 ; ++ i )
{
if ( target[i] == 0 ) continue;
for ( int j = 0 ; j < s.length() ; ++ j )
{
if ( s[j] == i + 97 ) positions[i].push_back(j);
}
}
DFS_index_max = st.length();
vector<int> trail(0);
DFS_Enumeration(0, &trail); //Here I got an runtime error
for ( vector<int> vi : possibleCombinations )
{
int currentMax = 0;
for ( int i = 0 ; i < vi.size() ; ++ i )
{
if ( vi[i] > currentMax )
{
if ( i == vi.size() - 1 ) ++ answer;
currentMax = vi[i];
continue;
}
else
break;
}
}
cout << answer;
}
void DFS_Enumeration(int index, vector<int>* trail)
{
if ( index == DFS_index_max )
{
possibleCombinations.push_back(*trail);
return;
}
for ( int i = 0 ; i < positions[st[index] - 97].size() ; ++ i )
{
trail -> push_back(positions[st[index] - 97][i]);
DFS_Enumeration(++index, trail);
trail -> pop_back();
}
return;
}
首先，我在 中查找字符st，并根据需要将它们标记为在我的布尔数组目标中找到。
然后，我使用 DFS 枚举所有可能的组合。对于上面的“doomdogged”和“dg”的例子，d存在于0、4、9中。而g存在于6、7中。我会得到06、07、46、47、96、97。
最后，我计算那些有意义的，并输出答案。出于某种原因，我的代码无法正常工作，并在我标记的行中生成有关内存的运行时错误。