题目的意思就是给你一些字符串,然后从字符串里面找这样的字符串输出:

1、这个字符串在给出的列表里面

2、这个字符串由其中其他两个字符串组成。

一看就是字典树,建树,然后拆分字符串遍历,搜索就行。

然后,这个题map也可以做,代码量减少一倍,时间增加一倍。


代码:

自建字典树:

StatusAccepted
Time62ms
Memory8240kB
Length1167
LangC++
#include <iostream>
#include <cstdio>
#include <string>
#include <memory.h>
using namespace std;
#define MAX 27
#define STRMAX 50005
struct Dict{
    bool is;
    Dict *next[MAX];
    Dict(){
        is=0;
        for(int i=0;i<MAX;i++)next[i]=NULL;
    }
};
void Insert_item(Dict *p, string str){
    Dict *now = p;
    for(int i=0;i<str.size();i++){
        int x=str[i]-'a';
        if(now->next[x]==NULL)now->next[x]=new Dict;
        now = now->next[x];
    }
    now->is=1;
}
bool search_item(Dict *p, string str){
    Dict *now = p;
    for(int i=0;i<str.size();i++){
        int x=str[i]-'a';
        if(now==NULL||now->next[x]==NULL)return 0;
        now = now->next[x];
    }
    return now->is;
}
int main()
{
    string str[STRMAX];
    int pos=0;
    Dict *node = new Dict;
    while(cin>>str[pos]){
        Insert_item(node, str[pos++]);
    }
    for(int i=0;i<pos;i++){
        for(int j=1;j<str[i].size();j++){
            string a(str[i], 0, j);
            string b(str[i], j);
            if(search_item(node, a)&&search_item(node, b)){
                cout<<str[i]<<endl;
                break;
            }
        }
    }
    return 0;
}


使用map

StatusAccepted
Time156ms
Memory9232kB
Length502
LangG++
#include <iostream>
#include <map>
#include <cstdio>
using namespace std;
#define MAX 50005
map<string, int> str;
int main()
{
    string res[MAX];
    int cnt=0;
    while(cin>>res[cnt++]){
        str[res[cnt-1]]=1;
    }
    for(int i=0;i<cnt;i++){
        for(int j=1;j<res[i].size();j++){
            string a(res[i], 0, j);
            string b(res[i], j);
            if(str[a]&&str[b]){
                cout<<res[i]<<endl;
                break;
            }
        }
    }
    return 0;
}