在C++中删除字符串中连续重复的字符

Question

这是一个字符串问题。首先删除所有长度为1的重复连续子串，然后删除长度为2的子串，以此类推......例如，如果我们有这样一个字符串 -> abcababceccced，在删除长度为1的子串后，我们将得到abcababceced，在删除长度为2的子串后，我们将得到abcabced，在删除长度为3的子串后，我们将得到abced。这将是最终输出结果。

我已经想出了一个算法，但它的时间复杂度为O(n3)，这并不理想。我的算法如下：

char str[20]="abcababceccced";
int len=strlen(a);
 for(i=1;i<=len/2;i++){
     for(j=0;j<len;){
      bool flag=chk(a,j,i);//this function will check whether the substring starting at a[j] and a[j+i] of length i are same or not.
       if(flag){
        //remove the second same substring.
       }
       else 
         j=j+i;
      }
  }

如果有人能用C ++提供一个更简单的算法来解决这个特定问题，我将非常感激。

- Poulami

Answer 1

你可以通过“滑动”字符串相对于自身进行比较字符与字符，然后查找匹配的位置来构建一些东西。例如：

abcababceccced
-abcababceccced
-0000000001100-

abcababceced
--abcababceced
--0001100110--

不清楚它是否会更快，"顺序上"，但这只是从不同的角度看问题。

- Hot Licks

Answer 2

你可以用单次遍历完成：

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

int main()
{
  char str[] = "abbbbcaaaababbbbcecccedeeed";
  int len = strlen(str);
  int read_pos, write_pos, prev_char;

  prev_char = str[0] + 1;
  for (read_pos = 0, write_pos = 0; read_pos < len; read_pos++)
  {
    if (str[read_pos] != prev_char)
    {
      str[write_pos] = str[read_pos];
      write_pos++;
    }
    prev_char = str[read_pos];
  }
  str[write_pos] = '\0';

  printf("str = %s\n", str);
  return 0;
}

由于您总是写入小于或等于读取位置的位置，因此在使用字符串之前永远不会破坏它。

我已将prev_char初始化为与第一个字符明显不同的内容，但检查字符串长度是否为零也是有意义的。

- Omri Barel

---

这只做第一遍扫描。 - AShelly

@AShelly：你说得完全正确。请随意点踩 :-(。我有一种感觉，原始问题可以使用后缀树非常高效地解决。类似这样的东西：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.6378 - Omri Barel

为什么不将这个添加到你的回答中，而不是引起负评呢 :) - AShelly

Answer 3

确实，对于每个子字符串长度都可以使用线性时间，因为您只想要连续的相同子字符串。只需保持一个计数器来计算相同字符数，并在找到子字符串时更新字符串。由于您想要删除所有可能长度的子字符串，因此总体复杂度为二次方。

以下C代码应该可以工作：

char str[20]="abcababceccced";
int len = strlen(str);
int i, j, counter;
for(i = 1; i <= len / 2; ++i)
{
   for(j = i, counter = 0; j < len; ++j)
   {
      if (str[j] == str[j - i])
         counter++;
      else
         counter = 0;
      if (counter == i)
      {
         counter = 0;
         memmove(str + j - i, str + j, (len - j) * sizeof(char));
         j -= i;
         len -= i;
      }
   }
   str[j] = 0;
   printf("%s\n", str);
}

这应该连续打印：

abcababceced
abcabced
abced

- FelixCQ