在字符串S1中删除字符串S2中所包含的字符

 1 /*************************************************************************
 2     > File Name: test.c
 3     > Author: ToLiMit
 4     > Mail: 348958453@qq.com 
 5     > Created Time: Sun 04 Jan 2015 06:20:05 PM PST
 6  ************************************************************************/
 7 
 8 #include<stdio.h>
 9 
10 void delete_str_char (char * main_str, char * sub_str)
11 {
12     if ((main_str == NULL) || (sub_str == NULL))
13         return;
14 
15     char * sub_index = sub_str;
16     char * main_index = main_str;
17     char bitmap[32] = {0};
18     char * str = (char *)malloc (strlen (main_str) + 1);
19     char * index = str;
20     memset (str, 0, strlen (main_str) + 1);
21 
22     while (*sub_index != '') {
23         char suffix = ((*sub_index) / 8) - 1;
24         char offset = (*sub_index) % 8;
25 
26         bitmap[suffix] |= (0x1 << (8 - offset));
27         sub_index++;
28     }
29 
30     while (*main_index != '') {
31         char suffix = ((*main_index) / 8) - 1;
32         char offset = (*main_index) % 8;
33 
34         if ((bitmap[suffix] & (0x1 << (8 - offset))) == 0) {
35             *index = *main_index;
36             index++;
37         }
38         main_index++;
39     }
40 
41     *index = '';
42     memcpy (main_str, str, strlen (str) + 1);
43     free (str);
44     return;
45 }
46 
47 int main (int argc, char * argv[])
48 {
49     char test[] = "aabcdaaaaabcaacb";
50 
51     delete_str_char (test, "bcd");
52     printf ("%s
", test);
53     return 0;
54 }

1. 用bitmap标记sub_str中出现过的字符

2. 申请一段buffer, 长度与main_str一致

3. 遍历main_str, 如果字符没有出现在bitmap中, 就将字符写入到buffer中

4. 遍历结束后, buffer中的数据就是删掉了sub_str中出现过的数据

时间复杂度: O(n + m) n为main_str长度, m为sub_str长度

空间复杂度: O(n)