要求在s1中删除所有s2的字符，要用最快的算法

还是深信服笔试题：要求在s1中删除所有s2的字符，要用最快的算法。

 

最正常最普通思想就是先申请一个s1长度的空间temp，两次for循环，遍历s1的字符时，再遍历s2，是否在s2中找到，找到则跳出继续遍历s1，找不到则写到temp里；显然这个算法效率比较差；

 

主要因为在s2中可能有多个字符重复，这样对同个字符遍历了多次；同时s1中也有相同字符的话，那么这个遍历的次数就呈指数增长。

 

下面的思想就是不管s2长度多少，组长的字符是个有限的小集合；首先遍历s2找出这个小集合，然后遍历s1，看字符是否在小集合中；

 

对于是否在小集合中用下面方法非常快捷：

由于每个字符对应唯一asc码，就是一个整数，用类似于FD_SET的东东。譬如整数0-31，对应数组a[0]，

a[0]占32位，00000000000000000000000000000000，假如如果找到s2中asc码为31的字符，则将第32位置为1 00000000000000000000000000000001，然后遍历s1时，发现某个字符对应的标志位设置位1了说明s1有这个字符，跳过即可。说白了，这就是个hash的过程，只是所有字符对应整数唯一，不比再解决冲突问题。(这招在《编程珠玑》里学到的，嗷嗷有用)

 

#include <stdio.h>
#include <string.h>
#include <time.h>

#define SHIFT 5
#define NUM 1000
#define MASK 0x1f
#define BIT 32

int a[1 + NUM/BIT] = {0};

void set(int i)
{
    a[i>>SHIFT] |= (1 << (i & MASK));
}

void init(int i)
{
    a[i>>SHIFT] &= ~(1 << (i & MASK));
}

int test(int i)
{
    int k;
    k = a[i>>SHIFT] & (1 << (i & MASK));
    return k;
}

void S1_S2(char* pc1, char* pc2)
{
    char* pTemp1 = pc1;
    char* pTemp2 = pc2;

    while(*pTemp2 != '\0')
    {
        set((int)*pTemp2);
        pTemp2++;
    }

    while(*pTemp1 != '\0')
    {
        if(!test(*pTemp1))
        {
            printf("%c", *pTemp1);
        }
        pTemp1++;
    }

    printf("\n");
}

void main()
{
    char c1[] = "abcdefghijklmnopqrstuvwxyz";
    char c2[] = "acefhj";
    S1_S2(c1, c2);
}

上面是详细代码，主要处理函数就是S1_S2，