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

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

我已经发明了一种经过后算法，但它具有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++中为这个问题提出了一个不太复杂的算法，我将不胜感激。

来源

2011-08-07 Poulami

实际上，对于每个子串长度，线性时间是可能的，因为您只需要连续的相同子串。只需保留一个相同的字符，并在找到子字符串时更新字符串。既然你想删除所有可能长度的子串，整体的复杂度是二次的。

下面的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

来源

2011-08-07 14:48:24 FelixCQ

可以以单道次做到这一点：

#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初始化为与第一个字符完全不同的东西，但检查字符串的长度不为零是有意义的。

来源

2011-08-07 14:23:17

这只做第一遍。 – AShelly

@AShelly：你是对的。随意downvote :-(。我有一种感觉，原来的问题可以非常有效地使用后缀树来解决，像这样：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1。 1.46.6378 –

为什么不把它添加到你的答案，而不是邀请downvotes :) – AShelly

您可以通过将字符串相对于自身“滑动”来进行构建，比较字符与字符之间的关系，然后查找匹配的位置。例如：

abcababceccced 
-abcababceccced 
-0000000001100- 

abcababceced 
--abcababceced 
--0001100110--

尚不清楚，这将是任何更快，“订单明智的”，虽然 - 只是用不同的方式来看待这个问题。

来源

2011-08-07 14:26:36

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

回答

相关问题