knakul853

Untitled

Nov 26th, 2020 (edited)
614
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.      
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. void dfs(unordered_set<string>&dict, string s, vector<string>&ans,  string res){
  5.     if(s.size()==0){
  6.         ans.push_back(res);
  7.         return;
  8.     }
  9.    
  10.     for(int i=1; i<=s.size(); i++){
  11.        
  12.         string sub = s.substr(0, i);
  13.         if(dict.find(sub)!=dict.end()){
  14.             dfs(dict, s.substr(i), ans, res +(res.size()?" "+s.substr(0, i):s.substr(0, i)));
  15.         }
  16.     }
  17. }
  18.  
  19. void solve(){
  20.     int n;
  21.     cin >> n;
  22.     unordered_set<string>dict;
  23.     for(int i=0; i<n; i++){
  24.         string ss;
  25.         cin >> ss;
  26.         dict.insert(ss);
  27.     }
  28.     string s;
  29.     cin >> s;
  30.     vector<string>ans;
  31.    
  32.     dfs(dict, s, ans, "");
  33.    
  34.     sort(ans.begin(), ans.end());
  35.     for(int i=0; i<ans.size(); i++){
  36.         cout<<"("<<ans[i]<<")";
  37.     }
  38.     cout<<endl;
  39. }
  40.  
  41. int main() {
  42.     //code
  43.     int t;
  44.     cin >> t;
  45.     while(t--){
  46.         solve();
  47.     }
  48.     return 0;
  49. }
RAW Paste Data