在源字符串中删除字串中出现的字符

http://wansishuang.javaeye.com/blog/416557

【转了个描述，配合下自己写的代码】

输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入 ”They are students.” 和 ”aeiou” ，则删除之后的第一个字符串变成 ”Thy r stdnts.”

 

 

一个字符串中删除。但如何能够把效率优化到让人满意的程度，却也不是一件容易的事情。也就是说，如何在第一个字符串中删除一个字 符，以及如何在第二字符串中查找一个字符，都是需要一些小技巧的。 
 
首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个字符，需要把后面所有的字符往前移动一个字节 的位置。但如果每次删除都需要移动字符串后面的字符的话，对于一个长度为 n 的字符串而言，删除一个字符的时间复杂度为 O(n) 。而对于本题而言，有可能要 删除的字符的个数是 n ，因此该方法就删除而言的时间复杂度为 O(n2) 。 
 
事实上，我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我们可以设想，当一个字符需要被删除的时候，我们把它所占的位置让它后面的字符来 填补，也就相当于这个字符被删除了。在具体实现中，我们可以定义两个指针 (pFast 和 pSlow) ，初始的时候都指向第一字符的起始位置。当 pFast 指向的字符是需要删除的字符，则 pFast 直接跳过，指向下一个字符。如果 pFast 指向的字符是不需要删除的字符，那么把 pFast 指向的字符赋值给 pSlow 指向的字符，并且 pFast 和 pStart 同时向后移动指向下一个字符。这样，前面被 pFast 跳过的字符相当于被删除了。用这种方法，整个删 除在 O(n) 时间内就可以完成。 
 
接下来我们考虑如何在一个字符串中查找一个字符。当然，最简单的办法就是从头到尾扫描整个字符串。显然，这种方法需要一个循环，对于一个长度为 n 的字符串，时间复杂度是 O(n) 。 
 
由于字符的总数是有限的。对于八位的 char 型字符而言，总共只有 28=256 个字符。我们可以新建一个大小为 256 的数组，把所有元素都初始化为 0 。然 后对于字符串中每一个字符，把它的 ASCII 码映射成索引，把数组中该索引对应的元素设为１。这个时候，要查找一个字符就变得很快了：根据这个字符的 ASCII 码，在数组中对应的下标找到该元素，如果为 0 ，表示字符串中没有该字符，否则字符串中包含该字符。此时，查找一个字符的时间复杂度是 O(1) 。 其实，这个数组就是一个 hash 表。

#include

#include

#include

void RemoveStrInSub(char*&src,char*sub)

{

int buk[128];

char *p_sub=sub;

char *p_src=src;

int i=0;

memset(buk,0,128*4);

while(*p_sub)

{

buk[int(*p_sub)]++;

p_sub++;

}

while(*p_src)

{

if(0==buk[int(*p_src)])

{

src[i++]=*p_src;

}

p_src++;

}

src[i]='\0';

printf("\n");

}

int main()

{

char *src,*sub;

src=(char*)malloc(200);

sub=(char*)malloc(20);

printf("Please input the source string: ");

gets(src);

printf("Please input the sub string    :  ");

gets(sub);

printf("Src : %s\n",src);

printf("Sub: %s\n",sub);

RemoveStrInSub(src,sub);

printf("After removed : \n");

puts(src);

    system("pause");

    return 0;

}