Spy Syndrome 2

做法：字典树

• 先把单词反向并转成小写存入字典树中，然后通过深搜的方式来匹配合适的单词

• 在搜索的过程中，如果找到一个符合的单词，不要直接输出，要找到最合适的那个，如下面这组易错组

• 易错组：
  Input

  7
  kirkirk
  2
  rik
  krik

  Output

  rik krik

代码

// Problem: Spy Syndrome 2
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/111339
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n;
string s[N],str;
vector<string> ans;

struct Trie {
    int nex[1000010][26], cnt;
    int exist[1000010];  // 该结点结尾的字符串是否存在

    void insert(string s, int l, int id) {  // 插入字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
            p = nex[p][c];
        }
        exist[p]=id;
    }
    bool dfs(int i){
        if(i==str.length()) return 1;
        int p = 0;
        while(i<str.length()){
            int c=str[i]-'a';
            if(!nex[p][c]) break;
            p=nex[p][c];
            i++;
            if(exist[p]) {
                if(dfs(i)) {
                    ans.pb(s[exist[p]]);
                    return 1;
                }
            }
        }
        return 0;
    }
} t;

void solve(){
    cin>>n>>str;
    int m;cin>>m;
    rep(i,1,m){
        cin>>s[i];
        string ss=s[i];
        reverse(ss.begin(),ss.end());
        transform(ss.begin(),ss.end(),ss.begin(),::tolower);
        t.insert(ss,ss.length(),i);
    }
    t.dfs(0);
    reverse(ans.begin(),ans.end());
    for(string x:ans) cout<<x<<" ";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}