1

我真的不知道如何实现这个函数：函数应该接受一个指向整数的指针、指向字符串数组的指针和用于进程的字符串。函数应将交换' ch '组合的所有变体写入数组' @ '符号并将整数更改为该数组的大小。有处理示例：

choker => {"choker","@oker"}

chocho => {"chocho","@ocho","cho@o","@o@o"}

chachacha => {"chachacha","@achacha","cha@acha","chacha@a","@a@acha","cha@a@a","@acha@a","@a@a@a"}

我正在用 c 标准 99 写这个。所以这是草图：

int n;
char **arr;
char *string = "chacha";
func(&n,&arr,string);

和功能草图：

int func(int *n,char ***arr, char *string) {

}

所以我认为我需要创建另一个函数，它计算“ch”组合的数量并为此分配内存。我很高兴听到有关此算法的任何想法。提前致谢。

4

4 回答 4

0

首先，我将创建一个辅助函数，例如 countChs，它只会遍历字符串并返回'ch'-s 的数量。这应该很容易，因为不涉及字符串重叠。

当您有出现次数时，您需要为2^count strings分配空间，每个字符串（除了原始字符串）的长度为strlen(original) - 1。您还可以将 n 变量更改为等于 2^count。

分配空间后，只需遍历新表中的所有索引并用原始字符串的副本填充它们（strcpy() 或 strncpy() 复制），然后将 'ch' 替换为 '@' （那里是在线准备好的片段的负载，只需寻找“C字符串替换”）。

最后让你的 arr 指针指向新表。不过要小心——如果它以前指向其他数据，你应该考虑释放它，否则你最终会出现内存泄漏。

于 2012-12-03T00:30:16.933 回答
0

如果您想要替换字符串的所有变体，数组大小将包含2^n元素。其中n- “ch”子串的数量。所以，计算这将是：

int i = 0;
int n = 0;
while(string[i] != '\0')
{
    if(string[i] == 'c' && string[i + 1] == 'h')
        n++;

    i++;
}

然后我们可以使用数字的二进制表示。让我们注意，从0to递增整数2^n，第 i 个数字的二进制表示将告诉我们，哪个“ch”发生要改变。所以：

for(long long unsigned int i = 0; i < (1 << n); i++)
{
    long long unsigned int number = i;
    int k = 0;

    while(number > 0)
    {
        if(number % 2 == 1)
            // Replace k-th occurence of "ch"

        number /= 2;
        k++;
    }

    // Add replaced string to array
}

此代码检查二进制表示中的每一位，number如果第 k 位为 1，则更改第 k 个出现。更改第 k 个“ch”非常容易，我把它留给你。

此代码仅对出现 64 次或更少的情况有用，因为 unsignedlong long int只能保存2^64值。

于 2012-12-03T00:30:53.400 回答
0

您可以很容易地计算组合的数量：

char * tmp = string;
int i;
for(i = 0; *tmp != '\0'; i++){
    if(!(tmp = strstr(tmp, "ch")))
        break;
    tmp += 2; // Skip past the 2 characters "ch"
}

// i contains the number of times ch appears in the string.

int num_combinations = 1 << i;

// num_combinations contains the number of combinations. Since this is 2 to the power of the number of occurrences of "ch"
于 2012-12-03T00:25:17.240 回答
0

对于原始问题，您需要解决两个子问题：

  • 为变体数组分配空间
  • 计算变化

对于第一个问题，您需要找到一个数学函数，该函数f采用输入字符串中“ch”出现的次数并返回总变化的数量。根据您的示例f(1) = 1：f(2) = 4和f(3) = 8。这应该让您很好地了解从哪里开始，但重要的是要证明您的函数是正确的。归纳法是证明这一点的好方法。

由于您的替换过程可确保结果的长度与原始结果相同，因此您可以为每个单独的结果分配与原始长度相等的空间。

至于第二个问题，最简单的方法是使用递归，就像 nightlytrails 提供的例子一样。

您将需要另一个函数来获取您为结果分配的数组、结果的 a count、字符串的当前状态和index当前字符串中的 a。

调用时，如果在 之后不再出现“ch”，index则将结果保存在数组中的位置count和增量处count（因此下次您不会覆盖先前的结果）。

如果有任何“ch”超出index，则调用此函数两次（重复部分）。其中一个调用使用当前字符串的副本，并且仅将 递增index到刚好超出“ch”。另一个调用使用当前字符串的副本，其中“ch”替换为“@”，并将index增加到“@”之外。

确保没有内存泄漏。没有malloc匹配就不行free。使此解决方案起作用后，您可能会注意到它在内存中的作用很松散。它使用的超出了应有的范围。改进算法是读者的练习。

于 2012-12-03T00:49:01.777 回答