wa28求助
查看原帖
wa28求助
728448
mqmhaaaa1楼主2024/8/20 09:24
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=1e6+10;
ll n,m;
string ds,zc[N];
ll dp[N];
deque<ll>ans;
struct trie{
	ll nxt[M][30],tot,num[M];
	void add(string s,int id){
		ll u=0;
		for(int i=s.size()-1;i>=0;i--){
			ll v=s[i]-'a';
			if('A'<=s[i]&&s[i]<='Z')v+=32;
			if(!nxt[u][v])nxt[u][v]=++tot;
			u=nxt[u][v];
		}
		num[u]=id;
	}
	void find(string s){
		for(int i=0;i<s.size();i++){
			if(!i||dp[i-1]){
				ll u=0;
				for(int j=i;j<s.size();j++){
					ll v=s[j]-'a';
					if(!nxt[u][v])break;
					u=nxt[u][v];
					if(num[u]){
						dp[j]+=(i)?dp[i-1]:1;
						ans.push_back(num[u]);
					}
				}
			}
		}
		return;
	}
}jb;
int main(){
	cin>>n;
	cin>>ds;
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>zc[i];
		jb.add(zc[i],i);
	}
	jb.find(ds);
	while(!ans.empty()){
		int x=ans.front();ans.pop_front();
		cout<<zc[x]<<" ";
	}
	return 0;
}


2024/8/20 09:24
加载中...