c - 一个比简单的 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 的字符是错误的，则 >i 为 1，否则为零:

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是bad的长度，n是n的长度str;你的解决方案是 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;
}