A-B

前言：

前几天是半期考试，没错我这个学校有半期考试。因为我学的比较烂，所以复习花了好多时间，没有时间更新博客，以后我尽量做到日更，谢谢大家的支持。

题目描述：

本题要求你计算A−B。不过麻烦的是，A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串A−B。

输入格式：

输入在2行中先后给出字符串A和B。两字符串的长度都不超过104，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。

输出格式：

在一行中打印出A−B的结果字符串。

输入样例：

I love GPLT!  It's a fun game!
aeiou
结尾无空行！

输出样例：

I lv GPLT!  It's  fn gm!
结尾无空行！

思路：

这题的解法非常多，最简单的就是暴力写法了，对主串A的每一个字符做循环遍历模式串B中的字符，看是否相等，相等就不输出。但暴力解法的时间复杂度为N*N，而N的值可能很大，而这题的时间限制是在140ms内跑完，很有因为可能超时而不过，所以我们需要换一个办法。
这里我用的是空间换时间的思想，我们另外开辟一个Boolean类型的一维数组，大小为52，我们可以用这个数组来存储B中出现过的字符，比如B=”aB”，则只有boo[0]和bool[26]为true，其他的都为false。这样我们对于A中的字符只需要遍历一遍就可以知道是不是需要输出，true表示不输出，false表示输出，所以代码的空间复杂度只有N了。
但后面我发现串B中可能不止有字母，可能还要一些特殊字符，比如’!’,’ ‘,’?’，所以还需要一个字符数组来存储出现过的特殊字符，但由于特殊字符是比较少的，所以对这个数组进行遍历花不了多少时间，而且我们可以将这种情况放在判断语句的最后，这样下来，代码的时间复杂度在串很长时依然接近N，这样这道题就写出来了。

源码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//判断A的特殊字符是否在B中存在
bool judge(char a,char b[],int c){
    for(int i=0;i<c;i++){
        if(a==b[i]){
            return false;
        }
    }
    return true;
}
int main(){
    string a,b;//a为主串，b为模式串
    char special[100];//由于存储b中出现过的特殊字符
    int flag=0;
    bool word[52];//存储b中出现过的字母，成表
    memset(word,false,sizeof(word));//将表全置空，也就是false
    getline(cin,a);
    getline(cin,b);
    //对表进行初始化
    for(int i=0;i<b.length();i++){
        if(b[i]>='a'&&b[i]<='z'){
            word[b[i]-'a']=true;
        }else if(b[i]>='A'&&b[i]<='Z'){
            word[b[i]-'A'+26]=true;
        }else{
            special[flag]=b[i];
            flag++;
        }
    }
    //对a进行遍历，并对表进行随机查找
    for(int i=0;i<a.length();i++){
        if(a[i]>='a'&&a[i]<='z'){
            if(!word[a[i]-'a']){
                cout<<a[i];
            }
        }else if(a[i]>='A'&&a[i]<='Z'){
            if(!word[a[i]-'A'+26]){
                cout<<a[i];
            }
        }else{
            if(judge(a[i],special,flag)){//判断是否是b中的特殊字符
                cout<<a[i];
            }
        }
    }
    return 0;
}