一個比天真實施的strcspn（）

我必須弄清楚我的主題字符串是否有任何不好的字符（我絕對討厭某些字符）。所以如果我有一個名爲str (char *str)的字符串，並且如果找到字符串bad (char *bad)中的任何字符，字符串str將被拒絕。現在我可以用strcspn(str,bad)來檢查。但有人可以建議strcspn的實施可能是什麼？一個簡單的實現將檢查str的每個字符對bad的每個字符，如果找到匹配則拒絕str。一個比天真實施的strcspn（）

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

來源

2011-09-21 lovesh

。注意，在第一個片段在內的條件迴路應' 'bad [j]！='\ 0'''，而不是'bad [j] ='\ 0'''。 –

@Tamás謝謝。錯過了！糾正它。 – lovesh

如果str很長（或您要檢查對同一組的壞字符許多字符串），你可以通過創建一個查找表獲得一些性能提升大小爲256的其中元素我是1，如果用ASCII碼的字符我是壞的，否則爲零：

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）最壞的情況下，其中米是壞和Ñ長度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; 
}

來源

2011-09-21 11:06:02

謝謝。當我正在尋找'strcspn'的實現時，我偶然發現了[此鏈接]（http://sources.redhat.com/ml/libc-alpha/2005-06/msg00108.html），但無法理解它。表格驅動程序是否與您所討論的方法相同 – lovesh

是的，這是通常的表驅動方法。該鏈接中提到的實現使用了一個額外的變量，比如'marker'，它最初是1，並且在每次調用後都增加1。然後該表格用壞標記填充「marker」，並在第二個循環中與「marker」進行比較。當'marker'達到256（並且溢出到零）時，它被設置爲1，並且使用memset來清除表。所以，以一些額外的簿記爲代價，你可以漸近地擺脫'memset'的成本，但是你必須使'table'和'marker'成爲靜態或線程本地。 –

但你爲什麼需要'marker'？您可以將表格保存在靜態存儲器中並將其設置一次（對於錯誤字符，請將其設置爲非零）。 – lovesh

如果您關心最壞情況下的性能和/或線程安全性，下面是一個將表保存在堆棧上的變體。

#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]，由於無符號字符保證不會有陷阱表示。）

來源

2011-09-21 12:22:53

一個比天真實施的strcspn（）

回答

相關問題