лучше, чем наивная реализация strcspn ()

Question

Я должен выяснить, содержит ли моя строка темы какие-либо плохие символы (некоторые символы, которые я абсолютно ненавижу). поэтому, если у меня есть строка с именем str (char *str) и если найдены какие-либо символы в строке bad (char *bad), строка str отклоняется. Теперь я могу использовать strcspn(str,bad), чтобы проверить это. Но кто-нибудь может подсказать, какой может быть реализация strcspn? Наивной реализацией будет проверка каждого символа str на каждый символ bad и отклонение str, если совпадение найдено.

for(i=0;str[i]!='\0';i++)
  for(j=0;bad[j]!='\0';j++)
    if(bad[j]==str[i])
       return -1;   //reject string
return 1;    //accept string

или что-то вроде

for(i=0;str[i]!='\0';i++)
  if(strchr(bad,str[i]))   //will return non-NULL if str[i] is found in bad
    return -1;   //reject string
return 1;    //accept string

Answer 1

Если str очень длинный (или вы собираетесь проверять множество строк по одному и тому же набору плохих символов), вы можете получить некоторую производительность, создав таблицу соответствия размером 256, где элемент i равно 1, если символ с кодом ASCII i плохой, а ноль в противном случае:

int contains_bad(const char* str, const char* bad) {
    unsigned short int table[256];
    char* ch;

    /* Prepare the lookup table */
    memset(table, 0, 256);
    for (ch = bad; *ch != 0; ch++)
        table[*ch] = 1;

    /* Test the string */
    for (ch = str; *ch != 0; ch++)
        if (table[*ch])
            return -1;

    return 1;
}

Приведенный выше код является наихудшим случаем O (m + n), где m длина плохая и n длина стр ;Ваше решение - O (mn) наихудший случай.

---

Обновление : вот альтернативная версия функции, которая сохраняет таблицу поиска в статическом хранилище и очищает ее только один раз в каждом255 вызовов.

int contains_bad(const char* str, const char* bad) {
    static unsigned short int table[256];
    static unsigned short int marker = 255;
    char* ch;

    /* Prepare the lookup table */
    if (marker == 255) {
        memset(table, 0, 256);
        marker = 1;
    } else {
        marker++;
    }
    for (ch = bad; *ch != 0; ch++)
        table[*ch] = marker;

    /* Test the string */
    for (ch = str; *ch != 0; ch++)
         if (table[*ch] == marker)
             return -1;

    return 1;
}

Answer 2

Если вы заботитесь о производительности в худшем случае и / или о безопасности потоков, вот вариант, который сохраняет таблицу в стеке.

#include <limits.h>
#include <stddef.h>

int contains_bad(const char *str, const char *bad) {
  size_t hint[UCHAR_MAX];
  size_t len_bad;
  for (len_bad = 0; bad[len_bad]; len_bad++) {
    hint[(unsigned char)bad[len_bad] - 1] = len_bad;
  }
  for (; *str; str++) {
    size_t i = hint[(unsigned char)*str - 1];
    if (i < len_bad && *str == bad[i]) return 1;
  }
  return 0;
}

(Для языковых юристов: технически неинициализированный массив hint может иметь скрытые представления ловушек. Если вы знаете, что это значит, и действительно заботитесь о поведении программ на C на давно мертвых платформах, одно решение, если bad является набором и, следовательно, имеет не более UCHAR_MAX символов, должен изменить size_t hint[UCHAR_MAX] на unsigned char hint[UCHAR_MAX], так как без знака char гарантированно не будет иметь представление ловушек.)