学步园

题目：点击打开链接

题意：输入两次字符串，每次输入n、m个，判断n个字符串中,有几个没在m中出现

思路：可以用字典树，也可以用map。

首先是字典树的代码：

#include <stdio.h>
#include <string.h>
struct node
{
    int flag;
    int z[26];
} num[1000001];
char s[100];
char ss[100];
int ns=0;
int newnode()
{
    int p=ns;
    ns++;
    for(int i=0; i<26; i++)
    {
        num[p].z[i]=-1;
    }
    num[p].flag=0;
    return p;
}
void creat()
{
    int i,k;
    scanf("%s",s);
    k=strlen(s);
    int qian;
    qian=0;
    int p;
    for(i=0; i<k; i++)
    {
        if(s[i]>='A'&&s[i]<='Z')s[i]=s[i]-'A'+'a';//A-a;
        int t=s[i]-'a';
        if(num[qian].z[t]==-1)
        {
            p=newnode();
            num[qian].z[t]=p;
        }
        else p=num[qian].z[t];
        qian=p;
    }
    num[p].flag=1;
}
int su=0;
int len;
int Search(int rt)
{
    int j;
    int q=rt;
    for(j=0; j<len; j++)
    {
        if(ss[j]>='A'&&ss[j]<='Z')ss[j]=ss[j]-'A'+'a';//A-a;
        if(num[q].z[ss[j]-'a']==-1)return 0;
        q=num[q].z[ss[j]-'a'];
    }
    if(num[q].flag==1)
    {
        num[q].flag=0;
        return 1;
    }
    return 0;
}
int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        scanf("%d",&m);
        ns=0;
        int root=newnode();
        int nn=n;
        while(n--)
        {
            creat();
        }
        int sum=0;
        while(m--)
        {
            scanf("%s",ss);
            len=strlen(ss);
            sum+=Search(root);
          //  printf("%d\n",sum);
        }
        printf("%d\n",nn-sum);
    }
    return 0;
}
 

map的代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int main()
{
    int n,m;
    int i,j;
    string a;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        scanf("%d",&m);
        map<string,int>q;
        map<string,int>p;
        for(i=0;i<n;i++)
        {
            cin>>a;
            transform(a.begin(),a.end(),a.begin(),::tolower);
            q[a]++;
        }
        for(i=0;i<m;i++)
        {
            cin>>a;
            transform(a.begin(),a.end(),a.begin(),::tolower);
            if(q[a]!=0)
            {
                n--;
                q[a]=0;
            }
        }
        printf("%d\n",n);
    }

    return 0;
}