Найти, если строка содержит символ в С++ (повышение разрешено)

Ответ 1

Используйте std::string::find

if (str.find('|') != std::string::npos)
{
    // ...
}

Там вряд ли будет что-то более эффективное. O (n) - лучшее, что вы можете сделать. Стандартная реализация библиотеки должна быть практически оптимальной.

Ответ 2

Другой способ - использовать функцию strchr в соответствующей строке c_str:

if(strchr(str.c_str(), '|'))
{
    \\found
}

Не уверен, как он сравнивается с поиском std с точки зрения скорости, хотя...

Позиция найденного символа

size_t pos = strchr(str.c_str(),'|') - str.c_str();

Ответ 3

Добавление ответа Тома Таннера. Если вы не хотите делать какие-либо априорные вычисления, вы будете застревать в O (n), т.е. Существует линейная корреляция между длиной строки, которую вы ищете, и потреблением времени. Том предложил создать массив (или вектор) логических элементов, указывающий на наличие определенного символа. Для индексирования строки потребуется O (n) один раз, но тогда вы можете проверить любое количество символов в O (1) (постоянное время), если оно включено. Недостатком такого подхода является то, что вам понадобится много памяти (после того, как вы решите, что вам нужно поддерживать unicode).

В качестве компромисса вы можете использовать std:: set или подобное, сохраняя только символы, которые действительно существуют в вашей строке ввода. Потребление памяти тогда будет примерно линейным относительно количества различных символов в строке, но поиск будет равен O (log n), то есть логарифмическому по времени.

Конечно, вы должны измерить/профиль, а затем объясните, какой вариант использования вы фактически оптимизируете. Пока вы этого не сделаете, придерживайтесь того, что проще всего понять и прочитать.

Ответ 4

Из этот источник эмпирический тест, выполненный с помощью Visual Studio 2013 Компилятор показывает, что strchr работает примерно 2x быстрее, чем std::string:: find.

Ответ 5

Существует только один способ сделать это. Просто перебирайте строку, чтобы проверить, существует ли персонаж, которого вы ищете. Вы можете сделать это, используя функцию string::find, которая получает символ и возвращает первую позицию, которая встречается в строке, или string::npos, если это значение отсутствует. Вы также можете использовать std::find, который получает два итератора, begin и end и значение ключа 'k' и возвращает итератор, указывающий на первое вхождение k в диапазоне [begin, end] или end, если k не найден. И, конечно, вы можете реализовать функцию find самостоятельно, например:

string::size_type pos=string::npos;
for(string::size_type i=0; i<s.size(); ++i) {
  if(s[i] == key) {
     pos=i;
     break;
  }
}
if(pos != string::npos) {
  // key was found
} else {
  // not found
}

или это:

string::iterator pos=s.end();
for(string::iterator i=s.begin(); i!=s.end(); ++i) {
  if(*i == key) {
    pos=i;
    break;
  }
}
if(pos != s.end()) {
  // found
} else {
  // not found
}

Подробнее о std::string::find и std::find:

• http://www.cplusplus.com/reference/string/string/find/
• http://www.cplusplus.com/reference/algorithm/find/

Ответ 6

Учитывая ваше утверждение о том, что вы хотите что-то быстрее, чем string:: find, единственное, о чем я могу думать, это создать класс, который имел высоко настраиваемые операторы присваивания, которые при каждом обновлении строки обновляли внутреннюю таблицу, содержащую первая позиция в строке любого возможного символа (256 для строки char, 65536 (?) для широкой строки). Это имеет O (1) поиск за счет довольно большой сложности, добавленной к неконстантным операциям.

Ответ 7

Вы можете попробовать следующее:

   string s1 = "Hello";
   string s2 = "el";
   if(strstr(s1.c_str(),s2.c_str()))
   {
    cout << " S1 Contains S2";
   }