0

Web サイトから問題が発生しました。string sandが与えられた場合、instのすべての可能な組み合わせを見つけなければなりません。例えば、sts

s      = "doomdogged"
st     = "dg"
answer = 4

d は 0 または 4 から、g は 6 または 7 から選択できます。これにより、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 が得られます。

最後に、意味のあるものを数えて、答えを出力します。何らかの理由で、コードが機能せず、マークした行でメモリに関する実行時エラーが発生します。

4

1 に答える 1

0

DFS_Enumerationindexは何度でも増加するst[index]可能性があるため、文字列の末尾を超える可能性がありますst。

于 2013-03-01T03:58:54.047 に答える