Как я могу реализовать эффективную замену строки из целого слова в C без регулярных выражений?

ProgramBox

Как я могу реализовать эффективную замену строки из целого слова в C без регулярных выражений?

Post author:admin
Запись опубликована:1 мая, 2023
Post category:Вопросы по программированию

#c #visual-c #string

#c #visual-c #строка

Вопрос:

Возможно, я упускаю из виду что-то очевидное, но мне было интересно, каким может быть самый быстрый способ реализовать замену строки из целого слова в C . Сначала я рассматривал простое объединение пробелов в искомом слове, но при этом не учитываются границы строки или знаки препинания.

Это моя текущая абстракция для замены (не целого слова):

 void Replace(wstringamp; input, wstring find, wstring replace_with) {
  if (find.empty() || find == replace_with || input.length() < find.length()) {
      return;
  }
  for (size_t pos = input.find(find); 
              pos != wstring::npos; 
              pos = input.find(find, pos)) {

      input.replace(pos, find.length(), replace_with);
      pos  = replace_with.length();
  }
}

Если я рассматриваю пробелы только как границу слова, я, вероятно, мог бы реализовать это, сравнив начало и конец строки поиска со строкой поиска, чтобы покрыть границы строки, а затем выполнив замену (L ‘ ‘ find L»)…. но мне было интересно, существует ли более элегантное решение, которое эффективно включало бы пунктуацию.

Давайте рассмотрим слово как любой набор символов, разделенных либо пробелом, либо знаком препинания (для простоты скажем !»#$%amp;'()* ,-./ как минимум — что соответствует (c > 31 amp;amp; c < 48) ).

В моем приложении мне приходится вызывать эту функцию над довольно большим массивом коротких строк, которые могут включать различные Юникоды, которые я не хочу разбивать на новые слова. Я также хотел бы избежать включения каких-либо внешних библиотек, но STL подходит.

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

1. Примечание: Замена может быть очень медленной, если ввод длинный и вы выполняете замены в начале. Я бы рекомендовал выполнить конкатенацию в строковом буфере (например, std::stringstream), а затем перезаписать входные данные за один шаг.

2. Требование Unicode значительно усложнит задачу. Я знаю, что вы пытаетесь избежать регулярных выражений и добавления библиотек, но вы могли бы заглянуть в ICU — там есть функция замены на основе регулярных выражений ( regex docs ), и она позволит вам использовать метасимвол b «граница слова».

Ответ №1:

Я думаю, вы можете это сделать, выполняя сопоставление целых слов и делая это эффективно. Ключ в том, чтобы:

определите границы «целого слова», используя ‘std::isalpha’, который должен работать с Unicode и любой локалью.
замените «не на своем месте», создав отдельную строку «output», которую вы заменяете на «input» в конце обработки, вместо того, чтобы выполнять работу «на месте» над самой строкой «input».

Вот мой взгляд на вашу функцию:

 #include <cctype> // isalpha
#include <ciso646> // or, not
#include <string> // wstring

using std::size_t;
using std::wstring;

/// @brief Do a "find and replace" on a string.
/// @note This function does "whole-word" matching.
/// @param[in,out] input_string The string to operate on.
/// @param[in] find_string The string to find in the input.
/// @param[in] replace_string The string to replace 'find_string'
///            with in the input.
void find_and_replace( wstringamp; input_string,
                       const wstringamp; find_string,
                       const wstringamp; replace_string )
{
  if( find_string.empty()
      or find_string == replace_string
      or input_string.length() < find_string.length() )
  {
    return;
  }

  wstring output_string;
  output_string.reserve( input_string.length() );
  size_t last_pos = 0u;
  for( size_t new_pos = input_string.find( find_string );
       new_pos != wstring::npos;
       new_pos = input_string.find( find_string, new_pos ) )
  {
    bool did_replace = false;
    if( ( new_pos == 0u
          or not std::isalpha( input_string.at( new_pos - 1u ) ) )
        and ( new_pos   find_string.length() == input_string.length()
              or not std::isalpha( input_string.at( new_pos   find_string.length() ) ) ) )
    {
      output_string.append( input_string, last_pos, new_pos - last_pos );
      output_string.append( replace_string );
      did_replace = true;
    }
    new_pos  = find_string.length();
    if( did_replace )
    {
      last_pos = new_pos;
    }
  }
  output_string.append( input_string, last_pos,
                        input_string.length() - last_pos );

  input_string.swap( output_string );
}

P.S. Я не был уверен, чего ‘replace_all’ пытался достичь в вашем первоначальном примере, поэтому я удалил его из своего решения для наглядности.

P.P.S. Этот код был бы намного чище с регулярными выражениями. Можете ли вы полагаться на функциональность C TR1 или C 2011? Они предоставляют стандартную библиотеку регулярных выражений.

1. Немного подумав об этом за ночь и увидев ответ @Code_So1dier, я должен был отметить, что то, что определяет «целое слово» в вашем вопросе, сейчас немного туманно. Это строго пробел, просто не алфавитные символы или не буквенно-цифровые символы? Это решение изменило бы логику проверки границ, выполняемой внутри цикла for для моего примера. Например, если границы «всего слова» являются пробелами, то замените not std::isalpha( input_string.at( new_pos find_string.length() ) ) на std::isspace( input_string.at( new_pos find_string.length() ) ) .

2. В моем приложении мне, вероятно, нужно беспокоиться только о пробелах и знаках препинания, а разделение во всех юникодах нежелательно (отредактированный вопрос). Цель отказа от использования регулярных выражений — это обещание меньших накладных расходов и надежда на более быструю функцию, подходящую для этой единственной задачи. Это правда, что пары b, вероятно, достаточно для большинства приложений.

3. @sakatc Хорошо, итак, количество пробелов или знаков препинания — это граница «целого слова»; изменение моего примера путем замены на not std::isalpha( input_string.at( new_pos find_string.length() ) ) std::isspace( input_string.at( new_pos find_string.length() ) ) or std::ispunct( input_string.at( new_pos find_string.length() ) ) должно сработать. Одно замечание: вы хотите, чтобы ваш метод ограничивал содержимое аргумента ‘find_string’? Например, было бы запутанно, если бы пользователь отправил «/test», поскольку он содержит оба класса символов-разделителей «целого слова».

4. Я действительно не думаю, что необходимо учитывать границы слов в поисковом слове. Если программист пытается сопоставить строки из нескольких слов с помощью поиска по целому слову, то, по сути, он уже запросил сбой функции…. Я бы не стал делать слишком много дополнительной работы над этим. Сопоставление, например, смежных слов, таких как «foo bar», выходит за рамки того, что мне нужно, но если вы хотите изучить это, попробуйте сами ~

5. также, кстати, replace_all из предыдущего предназначался для рекурсивных замен и на самом деле не применяется к замене всего слова. Например, чтобы уменьшить избыточные переводы строк из буфера, вы могли бы сделать Replace(buffer,"nn","n",true); … Я уберу это из вопроса, поскольку здесь это неприменимо.

Ответ №2:

Это мой быстрый ответ, но я не знаю, насколько быстрым будет решение… Существует несколько решений этой проблемы:
1. Используя итераторы, сравните каждое слово (разделенное пробелом), воссоздавая строку для каждого вхождения:

 stringamp; remove_all_occurences(stringamp; s, const stringamp; str_to_remove, const stringamp; str_to_put){
                typedef string::size_type string_size;
                string_size i = 0;
                string cur_string;
                cur_string.reserve(s.size());

                // invariant: we have processed characters [original value of i, i) 
                while (i != s.size()) {
                // ignore leading blanks
                // invariant: characters in range [original i, current i) are all spaces
                    while (i != s.size() amp;amp; isspace(s[i]))
                      i;

                    // find end of next word
                    string_size j = i;
                    // invariant: none of the characters in range [original j, current j)is a space
                     while (j != s.size() amp;amp; !isspace(s[j]))
                        j  ;
                        // if we found some nonwhitespace characters 


                    if (i != j) {
                        // copy from s starting at the beginning to i, placing str to replace, and finishing with j to the end of s
                        cur_string = s.substr(i,j-i);
                        if(cur_string == str_to_remove){
                            s = s.substr(0,i)   str_to_put   s.substr(j,s.size() - j);
                        }
                        i = j;
                    }
                }
                return s;
            }

Тестирование программы:

 void call_remove_all_occurences(){
                string my_str = "The quick brown fox jumps over sleepy dog fox fox fox";
                cout << remove_all_occurences(my_str,"fox","godzilla") << endl;
            }

Вывод:

 The quick brown godzilla jumps over sleepy dog godzilla godzilla godzilla

Разбивая строку на vector, а затем проходя через vector и заменяя каждое вхождение — просто … у меня нет кода, но вы поняли идею…