Наиболее эффективный способ памяти для поиска в строке в C

Question

Какой самый эффективный для памяти способ поиска в строке в ANSI C? (вставьте код)

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

Answer 1

Это зависит от того, что вы ищете ... но strchr () или strstr () часто подходят. И это очень эффективно для памяти, так как они не используют дополнительную память.

Answer 2

Перемещение по одному символу за раз составляет Θ ((n-m + 1) m). Проверьте в алгоритмах Бойера-Мура и Кнута-Морриса-Пратта более эффективные способы поиска подстрок - оба равны O (n). Ваш удобный учебник алгоритмов должен обсудить их обоих. Стандартная функция strstr библиотеки C реализует одну или обе функции, так что используйте ее, вместо того, чтобы использовать свою собственную.

Answer 3

Полагаю, это зависит от того, что вы ищете, но линейный поиск / сравнение использует не больше памяти, чем две строки («host» и «token»). Например:

char host[] = "this is my string to search";
char token[] = "y st";
int k = 0;
while(host[k] != '\0'){
  for(int t=0; (token[t]!='\0' && host[k+t]!='\0');){
    if(host[k] == token[t]){
      t++;  // we matched the first char of token, so advance
    }
    else{   // no match yet, reset the token counter and move along the host string
      k++;
      t = 0;
    }
  }
  k++;
}

(Возможно, я не совсем уверен в реализации, но, надеюсь, вы поняли мою идею.)

Стоит обратить внимание и на библиотечные функции, такие как strstr.

Answer 4

Если вы ищете подстроку, то strstr очень эффективно использует память. и для символа strchr также очень эффективно использует память. Ни один не нуждается в дополнительном хранении.

Я не уверен, есть ли что-то еще, что вы ищете.

Answer 5

Карп Рабин просто использует четыре целых и имеет линейное среднее время. Он просто вычисляет хеш строки поиска и использует некоторые математические приемы, чтобы быстро получить хеш следующей подстроки, учитывая хеш подстроки перед ней.

Стандартная версия сталкивается с трудностями, потому что большинство языков не имеют истинного математического модуля, но Справочник структур данных и алгоритмов Гонне и Баэса-Ята имеет версию , которая использует размер слова неявное по модулю (это также быстрее).

Answer 6

В зависимости от вида поиска и граничных условий существует большое количество различных алгоритмов поиска подстроки в строке. большая коллекция доступна здесь: http://www -igm.univ-mlv.fr / ~ lecroq / string / index.html

Answer 7

Я недавно столкнулся с этой проблемой и просто хочу поделиться своими мыслями.

«Эффективное использование памяти», как я понял, это возможность поиска длинной строки размера M с учетом только N объема доступной памяти, M> N. Это альтернатива эффективному использованию памяти на символ, доступный в строке для поиск. И я чувствую, что может быть более уместным для встроенной среды оригинального плаката (которая может иметь большой объем памяти).

Независимо от того, какой алгоритм вы используете для сравнения (чем эффективнее, тем лучше), я бы предпочел использовать циклический буфер (который должен быть больше строки, которую вы ищете, возможно, по крайней мере, в 2 раза? ) и непрерывно загружать поток символов в буфер, пока продвигается алгоритм поиска. Алгоритм поиска должен знать, как обернуть круговой буфер (или добавить уровень косвенности, чтобы скрыть круговой буфер от алгоритма поиска).