如何迭代生成所有可能的字母和数字组合以匹配可变长度的字符串？

Question

我想编写一个迭代逻辑程序，其中有一个输入字符串，程序从长度 1 开始，尝试所有可能的字母和数字组合。如果未找到匹配项，它将尝试长度为 2 的所有可能的字母和数字组合，依此类推，直到找到与输入字符串的匹配项。

例如，

string input = "xG7a";
// loop all possible combinations for length 1, i.e., 0-9 then A-Z, then a - z
// check for all if matches the input string
// loop all possible combinations for length 2, i.e., 00-09, then 0A-0Z, then 0a - 0z. Then 
// for 10-19, then 1A-1Z, then 1a - 1z ... till z0-z9, then zA-zZ, then za - zz
// again check for all if matches the input string
// Keep doing this for lengths 3, 4, 5 and so on till it matches with the input string.
// exit with status success if match else keep going till infinity
// This example would exit at length 4 when it matches with "xG7a"

这里匹配的所有可能组合的数量是 (10 + 26 + 26 = 62) = 62^1 + 62^2 + 62^3 + ... 直到有一个匹配。

编辑更多详情：

这是编写暴力破解逻辑练习的一部分
事先不知道输入的字符串。上面的例子是为了说明。我已经弄清楚了其余的逻辑。生成的字符串被传递到哈希函数中，该函数生成哈希以与数据库中的密码哈希相匹配。因此，要生成的字符串具有动态特性。
事先知道密码串只有数字和大小写字母组成

预先感谢您的所有帮助。

Answer 1

创建一个包含所有可能字符的正确顺序的字符串：

 char charlist[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

然后对于您要检查的每个字符，循环遍历此字符串构建您的测试字符串并进行比较：

int i, found;
char str_to_test[5];
for (i=0, found=0; !found && i<strlen(charlist); i++) {
    str_to_test[0] = charlist[i];
    str_to_test[1] = 0;
    if (!strcmp(str_to_test, target_string)) {
        found = 1;
    }
}
if (found) {
    printf("found it!\n");
} else {
    printf("not found\n");
}

对每个子字符串在嵌套循环中重复。

Answer 2

你说 - 一些伪代码，我说 - 完整的工作程序！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MARGIN 5

// if you're getting errors due to redeclaration of 'strdup', just remove that
const char *strdup(const char *string) {
    const size_t len = strlen(string);
    char *dst = calloc(len + 1, sizeof(char));

    memmove(dst, string, len);

    return dst;
}

struct NumeralSystem {
    char *alphabet;
    size_t base;
};

struct Word {
    struct NumeralSystem ns;
    char *data; // the current combination, null-terminated
    unsigned int *_internal; // indices of the characters of 'data' in 'ns.alphabet' 
    size_t length, maxLength;
};

struct NumeralSystem NewSystem(const char *alpha) {
    struct NumeralSystem ret = {strdup(alpha), strlen(alpha)};

    return ret;
}

struct Word NewWordEmpty(const struct NumeralSystem ns, const size_t maxLength) {
    struct Word ret;

    ret.ns = ns;
    ret.data = calloc(maxLength + 1, sizeof(char));
    ret._internal = calloc(maxLength + 1, sizeof(unsigned int));
    ret.maxLength = maxLength;

    *ret._internal = 0;
    *ret.data = *ret.ns.alphabet;

    ret.length = 1;

    return ret;
}

struct Word NewWordPreset(const struct NumeralSystem ns, const char *data) {
    struct Word ret;

    ret.length = strlen(data);

    const size_t maxLength = ret.length + MARGIN;

    ret.ns = ns;
    ret.data = calloc(maxLength + 1, sizeof(char));
    ret._internal = calloc(maxLength + 1, sizeof(unsigned int));
    ret.maxLength = maxLength;

    memmove(ret.data, data, ret.length);

    for (size_t i = 0; i < ret.length; ++i) {
        const char *found = strchr(ns.alphabet, ret.data[i]);
        if (found == NULL) return NULL;

        ret._internal[i] = found - ns.alphabet;
    }

    return ret;
}

void EnlargeWord(struct Word *wrd) { // here, wrd->length - wrd->maxLength == 1
    const size_t newSize = wrd->maxLength + MARGIN;

    wrd->data = realloc(wrd->data, newSize * sizeof(char));
    wrd->_internal = realloc(wrd->_internal, newSize * sizeof(int));

    memset(wrd->data + wrd->maxLength + 1, 0, MARGIN);
    memset(wrd->_internal + wrd->maxLength + 1, 0, MARGIN);

    wrd->maxLength = newSize;
}

void DestroyWord(struct Word *wrd) {
    free(wrd->data), free(wrd->_internal);
}

struct Word *next(struct Word *wrd) {
    int len = (int)(wrd->length - 1); // this can be negative, see below

    // handle the overflow if current digit is equal to the last_digit of the alphabet
    //   1. last_digit -> first_digit
    //   2. go to previous position
    while ((len >= 0) && (wrd->_internal[len] == wrd->ns.base - 1)) {
        wrd->_internal[len] = 0;
        wrd->data[len--] = *wrd->ns.alphabet;
    }

    // if all the digits in the word were equal to the last_digit of the alphabet,
    // 'len' will be exactly (-1), and the word's length must increase
    if (len == -1) {
        wrd->data[wrd->length++] = *wrd->ns.alphabet;

        // UH-OH, we're about to run out of bounds soon!
        if (wrd->length > wrd->maxLength)
            EnlargeWord(wrd);

        return wrd;
    }

    // if 'len' is still nonnegative, it's the position of the digit
    // that we haven't increased yet
    wrd->data[len] = wrd->ns.alphabet[++wrd->_internal[len]];

    return wrd;
}


int main(void) {
    const struct NumeralSystem ns = NewSystem("abcdef");
    struct Word wrd = NewWordPreset(ns, "deadbeef");

    printf("%s\n", wrd.data);

    for (unsigned int i = 0; i < 30; ++i)
        printf("%s\n", next(&wrd)->data);

    DestroyWord(&wrd);

    return 0;
}

如何迭代生成所有可能的字母和数字组合以匹配可变长度的字符串？

How to iteratively generate all possible combinations of letters and numbers for matching with a variable length string?

c

algorithm

brute-force