Удаление последовательных повторяющихся символов в строке в C ++ - PullRequest
Новая
       3

Удаление последовательных повторяющихся символов в строке в C ++

4 голосов
/ 07 августа 2011

Это строковая проблема. Сначала удалите все повторяющиеся последовательные подстроки длиной 1, затем удалите подстроку длины 2 и т. Д., Например, если у нас есть такая строка -> abcababceccced После удаления подстроки длины 1 мы будемget 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 ++ для этой определенной проблемы.

Ответы [ 3 ]

1 голос
/ 07 августа 2011

Возможно, вы сможете что-то построить, "сдвинув" строку относительно себя, сравнив символ за символом, а затем найдя совпадения.Например: 

abcababceccced
-abcababceccced
-0000000001100-

abcababceced
--abcababceced
--0001100110--

Не ясно, что это будет быстрее, "по порядку", хотя - просто по-другому взглянуть на проблему.

0 голосов
/ 07 августа 2011

Действительно, линейное время возможно для каждой длины подстроки, поскольку вам нужны только последовательные идентичные подстроки.Просто держите счетчик идентичных символов и обновляйте строку, когда вы нашли подстроку.Поскольку вы хотите удалить подстроки всех возможных длин, общая сложность будет квадратичной.

Должен работать следующий код 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
0 голосов
/ 07 августа 2011

Вы можете сделать это за один проход: 

#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 чем-то, что определенно отличается от первого символа, но имеет смысл проверить, что длина строки не равна нулю.

...