"取3个字符串共有的字母集合"的算法题

今天终于把挂了4天的问题单搞定。回头想想，这几天的日子真可以用寝食难安来形容啊。看来想在公司混点钱也不容易，要费把子力气。晚上到vckbase上溜达，看到一道算法题目，不大的题目。于是就抽空磨磨刀了，快生锈了，嘿嘿。

取3个字符串共有的字母集合有没有好算法?4个呢,5个呢...
                             —— 一个ID叫做[1_]的朋友问！

没有仔细考虑算法，凭着直觉，抓起editplus和gcc就开始做，边做边构思，偶似乎又回到了9年前...（多么令人向往的高中生活，555）大约20分钟后，码出了下面这个砖块，偶抛出来了啊，小心……^_^

/*-----------------------------------------------------------*| 题目：取3个字符串共有的字母集合有没有好算法?4个呢,5个呢...        |
| ------------                                                |
| 备注：题意不是很清晰，我就以可见ascii码为例做做吧。:)             |
|       先来个不超过8个字串的通用做法:p                              |
| author: Spark Song                                          |
| date  : 2005-11-29                                          |
\*-----------------------------------------------------------*/
#include 
#include 

#define CHR_BEGIN  (0x20)
#define CHR_END    (0x7E) 
#define ARR_SIZE   (CHR_END+1)
unsigned char flag_set[ARR_SIZE];


//test str
unsigned char str1[] = "hello, world! hi, hoho! I do not know! ";
unsigned char str2[] = "every night I have a dream !";
unsigned char str3[] = "Bye bye, I am so sleepy.";

void filtrate(unsigned char * str, int order);

int main(int argc, char *argv[])
{
    int i;
    unsigned char flag;
    //initialize
    memset(flag_set, 0, sizeof(flag_set));
    
    //do ....
    filtrate(str1, 0);
    filtrate(str2, 1);
    filtrate(str3, 2);

    flag = (0x1 | 0x2 | 0x4);
    //output
    printf("Now, the char left are: \n");
    for (i = CHR_BEGIN; i<=CHR_END; i++)
        if ((flag_set[i] & flag) == flag)
            printf("%c", (unsigned char)i);
	printf("\n");
    return 0;
}

void filtrate(unsigned char * str, int order)
{
    int i, j, k;
    unsigned char * p;
    for (p = str; *p != '\0'; p++)
        flag_set[*p] |= (1<<order);
}

输出结果如下：

Now, the chars left are:
 Ie

这段下意识精神状态下写出的代码最能反映我当前的健康状况了，hoho。等明天睡清醒的时候来检查一下，看看最近参加打羽毛球、乒乓球、游泳等体育活动是不是确实增强了偶的体质！：）

-------------
乾坤一笑 写于2005年11月29日  转载请标明出处和原文链接 
--------------------next---------------------
函数说明：
strs： in， 字符串数组
n   ： in， 字符串数组长度
out ： out，共有字母集合
返回值：   共有字母集合长度
size_t foo( const char* const strs[], size_t n, char out[static 128] )
{
    unsigned char flag[128]={0}, f=0;
    size_t i,j;
    for( i=0; i    {
        const unsigned char* p;
        for( p=(const unsigned char*)strs[i]; *p!='\0'; ++p )
        {
            assert( *p < 128 );
            if( flag[*p] == f ) flag[*p] = f+1;
        }
        if( f == 0xFE )
        {
            for( j=0; j                flag[j] = ( flag[j]==0xFF ? 1 : 0 );
            f = 1;
        }
        else ++f;
    }
    for( i=0, j=0; i        if( flag[i] == f ) out[j++]=(char)i;
    return j;
}

补充说明：
1. 此代码使用C99标准，如果你的烂编译器不支持C99的话，请把参数申明中的static关键字去掉，自行保证out数组长度不小于128。
2. 其实只要把unsigned char flag[128]改为unsigned size_t flag[128]就可以免去if( f == 0xFE )那一大段。
--------------------next---------------------