我必须弄清楚我的主题字符串是否有任何不良字符(一些我绝对讨厌的字符)。因此,如果我有一个名为 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
最佳答案
如果 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;
}
关于c - 一个比简单的 strcspn() 更好的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7498624/