Эффективный способ удаления указанных символов из строки

Question

Например, если дана строка « Stackoverflow для каждого » и удалить «aeiou», функция должна преобразовать str в « Stckvrflw s fr vry n ».

У меня есть один массив символов строки: str [] и один массив символов для удаления: remove []

Мое решение: Loop str [] ищет каждый символ в remove []. Shift str [] всегда оставлял одно место. Я уверен, что лучше взломать возможно.

Answer 1

Сдвиг всей строки влево на одно место сделает алгоритм O (n ^ 2) эффективным. Вы можете сделать это на месте, в линейное время:

void Remove (char * src, const char * match) {
   char * dest = src;
   for (;;) { 
      char ch = *src++; 
      if (!strchr (match, ch)) *dest++ = ch;  // Copy chars that don't match
      if (!ch) break;                         // Stop when we copy over a null  
   }
}

Я предполагаю, что они обнуляются. Если это не так, то вы также должны передать длины и соответствующим образом изменить алгоритм. В частности, вы не сможете использовать strchr. Просто для полноты, вот версия, которая работает с массивами символов (не завершается нулем).

// Removes from str[] (of length strlen), all chars that are found
// in match[] (of length matchlen). Modifies str in place, and returns
// the updated (shortened) length of str. 
int Remove (char[] str, int srclen, char[] match, int matchlen) {
   int dst = 0, found;
   for (int src = 0; src < srclen; src++) { 
      char ch = str[src];  
      found = 0;           // Search if this char is found in match
      for (int i = 0; i < matchlen && !found; i++) 
         if (match[i] == ch) found = 1;
      if (!found) str[dst++] = ch;
   }
   return dst;
}

И, наконец, это настолько близко к O (n), насколько мы собираемся получить, я думаю. Я предполагаю, что здесь используются 8-битные символы, и создаю справочную таблицу, поэтому она должна выполняться в O (n) + O (m), где m - длина строки соответствия.

int Remove (char* str, int srclen, char* match, int matchlen) {
   bool found[256];
   for (int i = 0; i < 256; i++) found[i] = 0;
   for (int i = 0; i < matchlen; i++) found[match[i]] = 1; 

   int dst = 0;
   for (int src = 0; src < srclen; src++) { 
      char ch = str[src];  
      if (!found[ch]) str[dst++] = ch;
   }
   return dst;
}

Answer 2

Вот моя версия, оператор if исключен из цикла копирования:

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

int main( void ){
  unsigned char str[]    = "Stackoverflow is for every one";
  unsigned char remove[] = "aeiou";

  unsigned char table[256] = { [ 0 ... 255 ] = 1 };
  for( unsigned char *r=remove; *r; r++ ){ table[*r]=0; }

  unsigned char *source=str, *dest=str;
  while( (*dest = *source++) ) dest += table[*dest];

  printf( "str: '%s'\n", str );
}

Answer 3

Я считаю, что это одна из тех «классических» головоломок.

По сути, вы сканируете строку 'match' и создаете таблицу битов поиска возможных совпадений.

Затем вы один раз проходите через 'src', проверяя каждый символ на своем столе.

O (n) время.

Алгоритм примерно такой:

   static char bits[32];  // Not thread-safe, but avoids extra stack allocation
   char * dest = src;
   memset(bits, sizeof(bits), 0);  
   for (; *remove; remove++)
   {
      bitfields[*match >> 3] |= *remove & 7;
   }

   for (;*src; src++) 
   {
      if (!((bits[*src >> 3] & (*src & 7)) == (*src & 7)))
      { 
        *dest++ = *src;
      }
   }

Я считаю, что ischr (), isdigit (), isspace () и т. Д. Работают аналогично этому методу, но их таблицы поиска постоянны.

Answer 4

Использование регулярных выражений для поиска и замены - более компактное решение. Используйте библиотеку GNU C или найдите другую, которая поддерживает поиск и замену регулярных выражений. Конечно, если символы меняются каждый раз, вам придется создавать регулярные выражения во время выполнения. Если вы придерживаетесь своего текущего подхода, разделите его на функции.

Мне также нравится подход Таридона. Это меньше работы !!

Answer 5

Если вы можете позволить себе еще один буфер, вы можете: Цикл str [] ищет каждый символ в remove [], но вместо shift копирует в новый массив.

Answer 6

Я бы зациклил str [] и сохранил каждый символ, который не существует в remove [], в новый массив (скажем, new_str []). Затем замените new_str [] на str [].