0

我正在尝试使用递归函数来进行通配符扩展。星号“*”可以扩展为 0-n 个字符。

示例：模式 '*b*' 将扩展为 'bb*'，星号被移除而 'bb' 保留。到目前为止，一切都很好。模式 '*b*' 也将扩展为 '*bb'，去掉星号，保留 'bb'。这会创建一个副本。

我的问题是我的递归代码是否存在根本性错误。我的目标是让扩展不会产生重复。下面的递归代码是最低限度的，我已经添加了代码，因此很容易看到唯一的字符串和重复的字符串。

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// Forward declarations
void WildcardExpansion(const char* key, int nodeLevel);    
size_t SeparateDuplicates(vector<string>& vec, vector<string>& dup);

// Global varables
int g_maxWordLen;
int g_minWordLen;
vector <string> g_words; // Generated words here

int main()
{
    int d, u, i;
    vector<string> duplicates;

    g_maxWordLen = 2;    // Max length of generated words
    g_minWordLen = 2;    // Min length

    WildcardExpansion("*b*", 0);                // Collects all generated words in g_words
    SeparateDuplicates(g_words, duplicates);    // Separates the duplicates from g_words

    u = (int)g_words.size();       // Size of unique words
    d = (int)duplicates.size();    // Size of duplicated words
    printf("Unique count: %d\n", u);
    for (i = 0; i < u; i++)
        printf("%s\n", g_words[i].c_str());
    printf("Duplicate count: %d\n", d);
    for (i = 0; i < d; i++)
        printf("%s\n", duplicates[i].c_str());
    return 0;
}
////////////////////////////////////////////////////////////////////////
// Recursive function to do wildcard expansion
// Key can contain one or more wildcards, '*' but not in sequence
// (** is equal to * but is not handled here)
//
void WildcardExpansion(const char* key, int charPos)
{
    int letter;
    int keyLen;
    int astCount;
    char c;
    char* p;
    char keyX[20];

    strcpy(keyX, key);
    astCount = 0;
    p = keyX;
    while (*p)                                // Count asterisks
        if (*p++ == '*')
            astCount++;
    keyLen = (int)strlen(keyX) - astCount;    // Letter count
    if (keyLen > g_maxWordLen)
        return;                               // Too long word

    do // while c 
    {
        c = key[charPos];
        switch (c)
        {
        case '*':         // -> key[nodeLevel] == '*'
        {
            //
            // Remove one asterisk
            //
            strcpy(keyX + charPos, key + charPos + 1);
            WildcardExpansion(keyX, charPos);            // Recurs same level
            strcpy(keyX, key);                           // Copy original with wildcard back for replacement below
            //
            // Replace * with letter a-z
             // *b* -> bb* -> bb AND *b* -> *bb -> bb => Duplicates!
            //
            for (letter = 0; letter < 26; letter++)
            {
                keyX[charPos] = ('a' + letter);                // Replace * with letter
                strcpy(keyX + charPos + 1, key + charPos);     // Expanded: abc -> abc* 
                WildcardExpansion(keyX, charPos + 1);          // Recurs next level
            }
            return;
        } // *
        case '\0':    // Found a complete word without wildcards
        {
            if (keyLen < g_minWordLen)
                return;
            g_words.push_back(key);
            break;
        }
        default:    // Dive deeper
        {
            charPos++;
        }
        } // switch
    } while (c);
}
///////////////////////////////////////////////////////////////////////
// Helper function to store the duplicates in a separate vector
//
size_t SeparateDuplicates(vector<string>& vec, vector<string>& dup)
{
    typename std::vector<string>::iterator it;

    std::sort(vec.begin(), vec.end());
    it = unique(vec.begin(), vec.end(), [&dup](auto& first, auto& second) -> bool
        {
            if (first == second)
            {
                dup.push_back(second);
                return true;
            }
            return false;
        });
    vec.resize(distance(vec.begin(), it));
    return dup.size();
}

输入“*b*”，输出长度2。观察输出：

Unique count: 51
ab
ba
bb
bc
bd
be
bf
bg
bh
bi
bj
bk
bl
bm
bn
bo
bp
bq
br
bs
bt
bu
bv
bw
bx
by
bz
cb
db
eb
fb
gb
hb
ib
jb
kb
lb
mb
nb
ob
pb
qb
rb
sb
tb
ub
vb
wb
xb
yb
zb
Duplicate count: 1
bb
4

0 回答 0