删除C中字符串中连续重复的字符
发布时间：2020-12-16 06:57:14 所属栏目：百科 来源：网络整理
导读：它是一个字符串问题.首先删除长度为1的所有重复连续子字符串,然后删除长度为2的子字符串,依此类推…… 例如,如果我们有这样的字符串 – abcababceccced 删除长度为1的子字符串后,我们将获得abcababceced 删除长度为2的子字符串后,我们将被删除 删除长度为3的
|
它是一个字符串问题.首先删除长度为1的所有重复连续子字符串,然后删除长度为2的子字符串,依此类推……
例如,如果我们有这样的字符串 – > abcababceccced 删除长度为1的子字符串后,我们将获得abcababceced 删除长度为2的子字符串后,我们将被删除 删除长度为3的子字符串后,我们将被删除 这将是最终输出 我设计了一种算法,但它的复杂度为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中为这个问题想出一个不太复杂的算法,我将非常感激. 解决方法
实际上,每个子串长度的线性时间是可能的,因为您只需要连续相同的子串.只需将计数器保留为相同的字符,并在找到子字符串时更新字符串.由于您要删除所有可能长度的子字符串,因此整体复杂性是二次的.
以下C代码应该正常工作： char str[20]="abcababceccced";
int len = strlen(str);
int i,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("%sn",str);
}
这应该连续打印： abcababceced abcabced abced （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |