在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++中刪除字符串中的連續重複字符

回答

相關問題