possible sentences

题解：

考察点： 深度优先搜索，字典树，剪枝

易错点：

本题的输入不是直接可用的，需要对输入进行字符串解析，同时由于输入带有空格，如果直接用会无法读入，建议使用按行进行读入。对于输入的解析，建议使用标记法，设置一个变量，当处于有效区域时，把标记为，当处于无效区域时，把标记为。这样保证有效部分能够很好的被解析出来。

本题的输出结果是按照字典序从大到小降序输出的。

方法一：深度优先搜索+剪枝

这题最直观的想法就是，对于字符串中每个位置，如果其前缀在集合中能找到，其可以以它为起点，往后找寻剩余部分是否在集合中，如果在集合中，则可以继续往后递归。这里加入一个剪枝，表示从到是否满足条件，如果在进行以后发现剩余部分并没有满足条件的字符串，则可以进行剪枝，说明枚举这个位置已经没有意义了

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e3+10;
int vis[maxn];
void Input(string &str,vector<string>&dict){  //读入数据
    string s,s1;
    getline(cin,s1);
    getline(cin,s);
    int flag=0;
    for(int i=0;i<s1.length();i++){
        if(!flag){
            if(s1[i]=='\"') flag=1;
            continue;
        }else{
            if(s1[i]=='\"'){
                flag=0;
            }else{
                str+=s1[i];
            }
        }
    }
    flag=0;
    string res="";
    for(int i=0;i<s.length();i++){
        if(!flag){
            if(s[i]=='\"') flag=1;
            continue;
        }else{
            if(s[i]=='\"'){
                flag=0;
                dict.push_back(res);
                res="";
            }else{
                res+=s[i];
            }
        }
    }
}
void dfs(string str,vector<string>dict,vector<string>&res,int pos,string t){
    if(pos==str.length()){
        res.push_back(t.substr(0,t.size()-1));
    }
    for(int i=pos;i<str.length();i++){
        string word=str.substr(pos,i-pos+1);
        if(find(dict.begin(),dict.end(),word)!=dict.end()&&!vis[i+1]){
            t.append(word).append(" ");
            int h=res.size();
            dfs(str,dict,res,i+1,t);
            if(h==res.size()) vis[i+1]=1;
            t.resize(t.size()-word.size()-1);
        }
    }
}
int main()
{
    string str="";
    vector<string>dict;
    Input(str,dict);
    memset(vis,0,sizeof(vis));
    vector<string>res;
    string t="";
    dfs(str,dict,res,0,t);
    sort(res.begin(),res.end());
    if(res.size()==0){
        cout<<"[]"<<endl;
    }else if(res.size()==1){
        cout<<"["<<res[0]<<"]"<<endl;
    }else{
        for(int i=res.size()-1;i>=0;i--){
            if(i==res.size()-1){
                cout<<"[";
                cout<<res[i];
            }else{
                cout<<", "<<res[i];
                if(i==0) cout<<"]"<<endl;
            }
        }
    }
    return 0;
}

方法二：字典树优化

在上述算法中，每次需要在集合中查询单词是否存在，如果集合很小还好，当集合非常大的时候，复杂度就会变得很高。可以引入字典树来进行优化。字典树由被称为前缀树，能在O(单词长度)的时间复杂度内查询单词是否存在与集合中，极大提升了查询的效率。关于字典树，网上资料很多，这里为同学们提供一份比较好用的模板

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e3+10;
int vis[maxn];
int trie[maxn][26],tot;
bool End[maxn];
void insert(string str){
    int len=str.length(),p=1;
    for(int k=0;k<len;k++){
        int ch=str[k]-'a';
        if(trie[p][ch]==0) trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    End[p]=true;
}
bool search(string str){
    int len=str.length(),p=1;
    for(int k=0;k<len;k++){
        p=trie[p][str[k]-'a'];
        if(p==0) return false;
    }
    return End[p];
}
void Input(string &str){  //读入数据
    string s,s1;
    getline(cin,s1);
    getline(cin,s);
    int flag=0;
    for(int i=0;i<s1.length();i++){
        if(!flag){
            if(s1[i]=='\"') flag=1;
            continue;
        }else{
            if(s1[i]=='\"'){
                flag=0;
            }else{
                str+=s1[i];
            }
        }
    }
    flag=0;
    string res="";
    for(int i=0;i<s.length();i++){
        if(!flag){
            if(s[i]=='\"') flag=1;
            continue;
        }else{
            if(s[i]=='\"'){
                flag=0;
                insert(res);
                res="";
            }else{
                res+=s[i];
            }
        }
    }
}
void dfs(string str,vector<string>&res,int pos,string t){
    if(pos==str.length()){
        res.push_back(t.substr(0,t.size()-1));
    }
    for(int i=pos;i<str.length();i++){
        string word=str.substr(pos,i-pos+1);
        if(search(word)&&!vis[i+1]){
            t.append(word).append(" ");
            int h=res.size();
            dfs(str,res,i+1,t);
            if(h==res.size()) vis[i+1]=1;
            t.resize(t.size()-word.size()-1);
        }
    }
}
int main()
{
    string str="";
    Input(str);
    memset(vis,0,sizeof(vis));
    vector<string>res;
    string t="";
    dfs(str,res,0,t);
    sort(res.begin(),res.end());
    if(res.size()==0){
        cout<<"[]"<<endl;
    }else if(res.size()==1){
        cout<<"["<<res[0]<<"]"<<endl;
    }else{
        for(int i=res.size()-1;i>=0;i--){
            if(i==res.size()-1){
                cout<<"[";
                cout<<res[i];
            }else{
                cout<<", "<<res[i];
                if(i==0) cout<<"]"<<endl;
            }
        }
    }
    return 0;
}