633C - Spy Syndrome 2 - CodeForces Solution

// Problem: C. Spy Syndrome 2
// Contest: Codeforces - Manthan, Codefest 16
// URL: https://codeforces.com/problemset/problem/633/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll  = long long;
using ull = unsigned long long;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(v)  (int)v.size()
#define all(v) v.begin(),v.end()
#define imax(a,b) ((a)>(b)?(a):(b))
#define imin(a,b) ((a)<(b)?(a):(b))
#define mem(a,v) memset(a,(v),sizeof(a))
#define MT int T; cin>>T; rep(_,1,T)
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define rep_(i,a,b) for(int i=a; i>=b; i--)
#define de(a) cout<<"DEBUG:"<<(a)<<'\n'
#define de2(a,b) cout<<"DEBUG:"<<(a)<<' '<<(b)<<'\n'
#define eps 1e-6

const int inf = INT_MAX;
const ll llinf = LLONG_MAX;

ll gcd(ll a, ll b) {return b==0?a:gcd(b,a%b);}
#define N (int)1e6+10
//数组模拟字典树
int tr[N][26],ed[N],dp[N],last[N],num[N],n,m,nb;
string a[N],S;
vector<int> ansidx;
string tran(string s){
	string ans = "";
	for(char ch : s){
		ans.pb(tolower(ch));
	}
	return ans;
}
void insert(int id,string s){
	int l = sz(s), b=0;
	rep(i,0,l-1){
		int t = s[i]-'a';
		if(tr[b][t]==0) tr[b][t]=++nb;
		b = tr[b][t];
	}
	ed[b]=id; //在结尾处标记id，以还原字符串的构造
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>S>>m; S=" "+S;
    rep(i,1,m){
    	cin>>a[i];
        insert(i,tran(a[i]));
    }
    dp[0]=1;
    rep(i,1,n){
    	int trp=0,b=i; //字典树指针 和 主串上的指针
    	while(b>0){
    		if(tr[trp][S[b]-'a'] ==0) break;
    		//树指针往下移动，串指针左移
    		trp = tr[trp][S[b]-'a'];
    		b--;
    		
    		//dp[i] = dp[j] & s[j+1:i] \in a[]
    		if(ed[trp] and dp[b]){
    			last[i] = b; //记录左边单词首字母索引
    			dp[i] = 1;
    			num[i] = ed[trp]; 
    			break; //dp[i] = true就可以停止了
    		}
    	}
    }
    //倒序还原
    int p = n;
    while(p){
    	ansidx.pb(num[p]);
    	p = last[p];
    }
    reverse(all(ansidx));
    for(auto idx : ansidx){
    	cout<<a[idx]<<' ';
    }
    return 0;
}