如果出现 k 次，则删除 String 中的相邻重复项---堆缓冲区溢出错误

Question

给定一个字符串 s 和一个整数 k，k 重复删除包括从 s 中选择 k 个相邻且相等的字母并删除它们，导致删除的子字符串的左侧和右侧连接在一起。我们在 s 上反复进行 k 重复删除，直到我们不再可以。我尝试了以下代码，它在一台机器（机器 1）中工作，并在另一台机器（机器 2）中抛出错误。

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

int sizeOfString(char * s)
{
    int count=0;
    while(s[count]!='[=10=]')
        count ++;
    
    return count;
}

int getSubString(char *source, char *target,int from, int to)
{
    int i=0,j=0;
    for(i=from,j=0;i<=to;i++,j++){
        target[j]=source[i];
    }
    target[j]='[=10=]'; 
    return 0;   
}

char * removeDuplicates(char * s, int k){
        int sizeString=sizeOfString(s);
        char *stringS= (char*)calloc(sizeString , sizeof(char));
        strcpy( stringS, s);
        int occuranceCount=1;
        int i=1;
        for (i=1;i<sizeString;i++)
        {
          if (s[i]==s[i-1])
          {
              occuranceCount++;
          }
          else{
              occuranceCount=1;
          }
          if (occuranceCount==k)
          {
              char *firstPart=(char*)calloc(i-k ,sizeof(char));
              getSubString(s,firstPart,0,i-k);
              char *secondPart=(char*)calloc(sizeString ,sizeof(char));
              getSubString(s,secondPart,i+1,sizeString-1);
              strcat(firstPart,secondPart);
              strcpy(s,firstPart);
              free (firstPart);
              free(secondPart);
              removeDuplicates(s,k);
          }
            
        }
    free(stringS);
    return s;
            
}

int main()
{
    char word[]="adbbbcccb";
    printf("after truncating the string is %s\n",removeDuplicates(word,3));
    return 0;
}

机器1输出：

after truncating the string is adb


...Program finished with exit code 0
Press ENTER to exit console.

机器 2 在 PC、BP 和 SPthe error is shown in the attached picture 的特定值处抛出堆缓冲区溢出错误。我做错了什么？

Answer 1

对于初学者来说，不清楚为什么你编写自己的函数 sizeOfString 而不是使用标准字符串函数 strlen 而另一方面你正在使用其他标准字符串函数，例如 strcpy 或 strcat.

要么你应该在所有需要标准字符串函数的地方使用标准字符串函数，要么你不应该完全使用标准字符串函数。

使用动态分配内存的方法效率低且不安全。

例如这个代码片段

    int sizeString=sizeOfString(s);
    char *stringS= (char*)calloc(sizeString , sizeof(char));
    strcpy( stringS, s);

导致内存溢出，因为没有为源字符串的终止零分配space。

函数有错误。例如，我们假设 k 等于 2 并且字符串以两个相等的字符开头。在这种情况下，您有（请参阅此代码片段）

   int occuranceCount=1;
    int i=1;
    for (i=1;i<sizeString;i++)
    {
      if (s[i]==s[i-1])
      {
          occuranceCount++;
      }
      else{
          occuranceCount=1;
      }
      if (occuranceCount==k)
      {
          char *firstPart=(char*)calloc(i-k ,sizeof(char));
          //...

i等于1，occuranceCount递增等于2，因为字符串的第二个字符等于字符串的第一个字符。因此，calloc 调用中的表达式 i - k 等于 -1，这会导致分配的内存大小无效，从而导致未定义的行为。

或者例如在这条语句之后

strcpy(s,firstPart);

以及函数本身的递归调用

removeDuplicates(s,k);

字符串的长度s和使用的索引i变得无效。所以for循环又会失效。

我可以建议下面的演示程序中显示的以下非递归函数。该函数不是基于使用标准 C 字符串函数，也不会动态分配内存。

#include <stdio.h>

char * removeDuplicates( char *s, size_t n )
{
    if ( n == 1 )
    {
        *s = '[=14=]';
    }
    else if ( n != 0 )
    {
        char *p = s;
        for ( char *q = s; *q; )
        {
            char c = *q;
            size_t i = 1;
            while ( i < n && *++q == c ) ++i;
            
            if ( i != n )
            {
                if ( p != q - i )
                {
                    while ( i ) *p++ = *( q - i-- );
                }
                else
                {
                    p += i;
                }
            }
            else
            {
                ++q;
            }
        }
        
        *p = '[=14=]';
    }
    
    return s;
}

int main(void) 
{
    char s0[] = "112223333";
    
    puts( removeDuplicates( s0, 0 ) );
    
    char s1[] = "112223333";
    
    puts( removeDuplicates( s1, 1 ) );
    
    char s2[] = "112223333";
    
    puts( removeDuplicates( s2, 2 ) );
    
    char s3[] = "adbbbcccb";
    
    puts( removeDuplicates( s3, 3 ) );
    
    return 0;
}

程序输出为

如果出现 k 次，则删除 String 中的相邻重复项---堆缓冲区溢出错误

Remove Adjacent Duplicates in String if the occurrence happens for k times--- heap buffer overflow error

c

duplicates

char

c-strings

function-definition