Manthan, Codefest 16 C

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#define LL long long

using namespace std;

const int MAXN = 10050;
const int MOD = 1e9 + 7;
char tmp[MAXN], str[MAXN];

struct Word{
	char s[1005];
	int len;
};
int n;
vector<Word>w;

int wmod[MAXN * 10];
int smod[1005];
int ymod[1005];
int dp[MAXN];

int main(){
	w.clear();
	int len;
	scanf("%d", &len);
	scanf("%s", tmp);
	scanf("%d", &n);
	ymod[0] = 1;
	for(int i = 1; i <= 1000; i++){
		ymod[i] = ((LL)ymod[i - 1] * 26) %MOD;
	}
	
	for(int i = len - 1; i >= 0; i--){
		str[len - i] = tmp[i];
	}
	str[len + 1] = '\0';
	int minlen = 0;
	Word tmps;
	for(int i = 0; i < n; i++){
		scanf("%s", tmps.s);
		tmps. len = strlen(tmps.s);
		w.push_back(tmps);
		minlen = max(minlen, tmps.len);
	}
	

	//cout << 0 << endl;
	
	for(int i = 0; i < n; i++){
		int val = 0; 
		int weight = 1;
		for(int j = 0; j < w[i].len; j++){
			val = ((LL)val + (LL)(w[i].s[j] >= 'A' && w[i].s[j] <= 'Z'? (w[i].s[j] - 'A') : (w[i].s[j] -'a')) * weight % MOD )%MOD;
			weight = (LL)weight * 26 % MOD;
		}
		wmod[i] = val;
	}
	/*
	for(int i = 0; i < n; i++)
		cout << wmod[i] << endl;
	*/
	memset(smod, -1, sizeof(smod));
	smod[0] = 0;
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	
	for(int i = 1; i <= len; i++){
		for(int k = minlen + 1; k >= 1; k--){
			if(smod[k - 1] == -1) continue;
			else{
				smod[k] = ((LL)smod[k- 1] + (LL)ymod[k - 1] *( str[i] - 'a' ))%MOD;
			}
		}
		for(vector<Word>::iterator k = w.begin(); k != w.end(); ++k){
			char ss = k->s[k->len - 1];
			ss = (ss >= 'A' && ss <= 'Z' )? ss -'A' +'a' : ss;
			if(ss != str[i] ) continue;
			else {
				if(smod[k ->len] != -1 && wmod[k - w.begin()] == smod[k->len] && dp[i - k->len] >= 0){
					dp[i] = k - w.begin();
					break;
				}
			}
		}
	}
	int i = len;
	while(i){
		printf("%s", w[dp[i]].s);
		i = i - w[dp[i]].len;
		if(i) printf(" ");
	}
	printf("\n");
	
}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 1E4 + 10;

struct T{
	int ch[26];
	int END;
	T () {
		memset(ch,0,sizeof(ch)); 
		END = 0;
	}
}t[1000010];

int cnt,n,m,f[maxn],last[maxn];
char x[maxn],y[1010];

vector <char> v[maxn*10];

void Insert(int o,int pos,int len,int num)
{
	for (; pos < len; pos++) {
		int to;
		if (y[pos] >= 'a') to = y[pos]-'a';
		else to = y[pos]-'A';
		if (!t[o].ch[to]) t[o].ch[to] = ++cnt;
		o = t[o].ch[to];
	}
	t[o].END = num;
}

void solve(int pos)
{
	int END = max(1,pos-999);
	int o = 0;
	for (int i = pos; i >= END; i--) {
		o = t[o].ch[x[i]-'a'];
		if (!o) break;
		if ((f[i-1] || i == 1) && t[o].END) {
			last[pos] = i;
			f[pos] = t[o].END; 
			break;
		}
	}
}

void pri(int pos)
{
	if (last[pos] != 1) pri(last[pos]-1);
	int len = v[f[pos]].size();
	for (int i = 0; i < len; i++) printf("%c",v[f[pos]][i]);
	printf(" ");
}

int main()
{
	#ifdef YZY
		   freopen("yzy.txt","r",stdin);
	#endif
	
	cin >> n;
	scanf("%s",1+x);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		scanf("%s",&y);
		int len = strlen(y);
		Insert(0,0,len,i);
		for (int j = 0; j < len; j++) v[i].push_back(y[j]);
	}
	
	for (int i = 1; i <= n; i++) 
		solve(i);
	pri(n);
	return 0;
}