Ideone.com

fork download

copy

#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;
 
const long double PI = acos(-1);
const long long MOD = 1000000000 +7;
 
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
 
ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}
 
ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}
 
ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}
 
ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}
 
ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}
 
int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
 
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}
 
int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}
 
/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/
 
const int N = 4000+5;
const int E = 26;
 
int n;
int l;
char a[N];
char v[N];
// Trie memory
int h[N];
int edges;
int ch[N];
int to[N];
int nodes;
int nxt[N];
bool pat[N];
int last[N];
int closest[N];
// DP memory
int memo[N][N][2];
 
void addNode(){
	pat[nodes] = false;
	last[nodes] = -1;
	nodes += 1;
}
 
void addEdge(int u, int v, int c){
	ch[edges] = c;
	to[edges] = v;
	nxt[edges] = last[u];
	last[u] = edges;
	edges += 1;
}
 
int find(int u, int label){
	for(int e = last[u]; e != -1; e = nxt[e]){
		if(ch[e] == label) return e;
	}
	return -1;
}
 
void insert(int npat){
	int pos = 0;
	for(int i = 0; v[i] ; i++){
		int nxt = v[i] - 'A';
		if(find(pos, nxt) == -1){
			h[nodes] = h[pos] + 1;
			addEdge(pos, nodes, nxt);
			addNode();
		}
		pos = to[find(pos, nxt)];
	}
	pat[pos] = true;
}
 
void DFS(int u){
	closest[u] = pat[u]? 0 : 1e9;
	for(int e = last[u]; e != -1; e = nxt[e]){
		int v = to[e];
		DFS(v);
		if(closest[v] + 1 < closest[u]){
			closest[u] = closest[v] + 1;
		}
	}
}
 
int solve(){
	DFS(0);
	n = strlen(a);
	vector<int> p(nodes);
	iota(all(p), 0);
	sort(all(p), [&] (int i, int j){
		return h[i] > h[j];
	});
	for(int stay = 0; stay < 2; stay++){
		for(int state = 0; state < nodes; state++){
			memo[n][state][stay] = state? closest[state] : 0;
		}
	}
	for(int pos = n - 1; pos >= 0; pos--){ // Posicion en a
		for(int stay = 0; stay < 2; stay++){ // Si puedo regresar a la raiz o no
			for(int state : p){ // Estado del trie
				int ans = 1e9;
				for(int e = last[state], cand; e != -1; e = nxt[e]){
					// Reemplazar a[pos]
					cand = (ch[e] + 'A' != a[pos]) + memo[pos + 1][to[e]][1];
					if(ans > cand) ans = cand;
					// Borrar la letra ch[e] y avanzar al siguiente estado de todas formas
					cand = 1 + memo[pos][to[e]][0];
					if(ans > cand) ans = cand;
				}
				// Reiniciar el string 
				if(stay) ans = min(ans, closest[state] + memo[pos][0][0]);
				// Borrar a[pos]
				ans = min(ans, 1 + memo[pos + 1][state][1]);
				memo[pos][state][stay] = ans;
			}
		}
	}
	return memo[0][0][1];
}
 
int main(){
	int t;
	ri(t);
	while(t--){
		ri(l);
		nodes = edges = 0;
		addNode();
		for(int i = 1; i <= l; i++){
			scanf("%s", v);
			insert(i);
		}
		scanf("%s", a);
		printf("%d\n", solve());
	}
	return 0;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBhbGwodikgKHYpLmJlZ2luKCksKHYpLmVuZCgpCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgcHBiIHBvcF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcmkoeCkgc2NhbmYoIiVkIiwmKHgpKQojZGVmaW5lIHJpMih4LHkpIHNjYW5mKCIlZCAlZCIsJih4KSwmKHkpKQojZGVmaW5lIHJpMyh4LHkseikgc2NhbmYoIiVkICVkICVkIiwmKHgpLCYoeSksJih6KSkKI2RlZmluZSBybGwoeCkgc2NhbmYoIiVsbGQiLCYoeCkpCiNkZWZpbmUgcmxsMih4LHkpIHNjYW5mKCIlbGxkICVsbGQiLCYoeCksJih5KSkKI2RlZmluZSBybGwzKHgseSx6KSBzY2FuZigiJWxsZCAlbGxkICVsbGQiLCYoeCksJih5KSwmKHopKQojZGVmaW5lIGdjKHgpICgoeCkgPSBnZXRjaGFyKCkpCnVzaW5nIG5hbWVzcGFjZTo6c3RkOwoKY29uc3QgbG9uZyBkb3VibGUgUEkgPSBhY29zKC0xKTsKY29uc3QgbG9uZyBsb25nIE1PRCA9IDEwMDAwMDAwMDAgKzc7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGxsLGxsPiBwbGw7CnR5cGVkZWYgcGFpcjxsbCxwbGw+IHRsbDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IGlpOwp0eXBlZGVmIHBhaXI8aW50LGlpPiBpaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPGlpPiB2aWk7CnR5cGVkZWYgdmVjdG9yPGlpaT4gdmlpaTsKdHlwZWRlZiB2ZWN0b3I8bGw+IHZsbDsKdHlwZWRlZiB2ZWN0b3I8cGxsPiB2cGxsOwp0eXBlZGVmIHZlY3Rvcjx0bGw+IHZ0bGw7CnR5cGVkZWYgdmVjdG9yPHN0cmluZz4gdnM7CnR5cGVkZWYgc2V0PGludD4gc2k7CnR5cGVkZWYgc2V0PGlpPiBzaWk7CnR5cGVkZWYgc2V0PGlpaT4gc2lpaTsKCmxsIGdjZChsbCBhLCBsbCBiKXsgcmV0dXJuIGI9PTA/YTpnY2QoYixhJWIpO30KCmxsIGFkZChsbCBhLCBsbCBiLCBsbCBtID0gTU9EKXsKCWlmKGEgPj0gbSkgYSAlPSBtOwoJaWYoYiA+PSBtKSBiICU9IG07CglpZihhIDwgMCkgYSArPSBtOwoJaWYoYiA8IDApIGIgKz0gbTsKCWxsIHJlcyA9IGErYjsKCWlmKHJlcyA+PSBtIG9yIHJlcyA8PSAtbSkgcmVzICU9IG07CglpZihyZXMgPCAwKSByZXMgKz0gbTsKCXJldHVybiByZXM7Cn0KCmxsIG11bChsbCBhLCBsbCBiLCBsbCBtID0gTU9EKXsKCWlmKGEgPj0gbSkgYSAlPSBtOwoJaWYoYiA+PSBtKSBiICU9IG07CglpZihhIDwgMCkgYSArPSBtOwoJaWYoYiA8IDApIGIgKz0gbTsKCWxsIHJlcyA9IGEqYjsKCWlmKHJlcyA+PSBtIG9yIHJlcyA8PSAtbSkgcmVzICU9IG07CglpZihyZXMgPCAwKSByZXMgKz0gbTsKCXJldHVybiByZXM7Cn0KCmxsIHBvd19tb2QobGwgYSwgbGwgYiwgbGwgbSA9IE1PRCl7CglsbCByZXMgPSAxTEw7CglhID0gYSVtOwoJd2hpbGUoYil7CgkJaWYoYiYxKSByZXMgPSBtdWwocmVzLGEsbSk7CgkJYiA+Pj0gMTsKCQlhID0gbXVsKGEsYSxtKTsKCX0KCXJldHVybiByZXM7Cn0KCmxsIGZhc3RleHAobGwgYSwgbGwgYil7CglsbCByZXMgPSAxTEw7Cgl3aGlsZShiKXsKCQlpZihiJjEpIHJlcyA9IHJlcyphOwoJCWIgPj49IDE7CgkJYSAqPSBhOwoJfQoJcmV0dXJuIHJlczsKfQoKaW50IGdjZEV4dGVuZGlkbyhpbnQgYSwgaW50IGIsIGludCAqeCwgaW50ICp5KXsKCWlmKGEgPT0gMCl7CgkJKnggPSAwOwoJCSp5ID0gMTsKCQlyZXR1cm4gYjsKCX0KCWludCB4MSwgeTE7CglpbnQgZ2NkID0gZ2NkRXh0ZW5kaWRvKGIlYSxhLCZ4MSwmeTEpOwoJCgkqeCA9IHkxLShiL2EpKngxOwoJKnkgPSB4MTsKCXJldHVybiBnY2Q7Cn0KCmludCBtb2RJbnZlcnNvKGludCBhLCBpbnQgbSl7CglpbnQgeCwgeTsKCWludCBnID0gZ2NkRXh0ZW5kaWRvKGEsbSwmeCwmeSk7CglpZihnIT0xKSByZXR1cm4gLTE7CgllbHNlIHJldHVybiAoeCVtICsgbSklbTsKfQoKLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKKioqKioqKioqKioqKlAqTCpBKk4qVCpJKkwqTCpBKioqKioqKioqKioqCioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwoKY29uc3QgaW50IE4gPSA0MDAwKzU7CmNvbnN0IGludCBFID0gMjY7CgppbnQgbjsKaW50IGw7CmNoYXIgYVtOXTsKY2hhciB2W05dOwovLyBUcmllIG1lbW9yeQppbnQgaFtOXTsKaW50IGVkZ2VzOwppbnQgY2hbTl07CmludCB0b1tOXTsKaW50IG5vZGVzOwppbnQgbnh0W05dOwpib29sIHBhdFtOXTsKaW50IGxhc3RbTl07CmludCBjbG9zZXN0W05dOwovLyBEUCBtZW1vcnkKaW50IG1lbW9bTl1bTl1bMl07Cgp2b2lkIGFkZE5vZGUoKXsKCXBhdFtub2Rlc10gPSBmYWxzZTsKCWxhc3Rbbm9kZXNdID0gLTE7Cglub2RlcyArPSAxOwp9Cgp2b2lkIGFkZEVkZ2UoaW50IHUsIGludCB2LCBpbnQgYyl7CgljaFtlZGdlc10gPSBjOwoJdG9bZWRnZXNdID0gdjsKCW54dFtlZGdlc10gPSBsYXN0W3VdOwoJbGFzdFt1XSA9IGVkZ2VzOwoJZWRnZXMgKz0gMTsKfQoKaW50IGZpbmQoaW50IHUsIGludCBsYWJlbCl7Cglmb3IoaW50IGUgPSBsYXN0W3VdOyBlICE9IC0xOyBlID0gbnh0W2VdKXsKCQlpZihjaFtlXSA9PSBsYWJlbCkgcmV0dXJuIGU7Cgl9CglyZXR1cm4gLTE7Cn0KCnZvaWQgaW5zZXJ0KGludCBucGF0KXsKCWludCBwb3MgPSAwOwoJZm9yKGludCBpID0gMDsgdltpXSA7IGkrKyl7CgkJaW50IG54dCA9IHZbaV0gLSAnQSc7CgkJaWYoZmluZChwb3MsIG54dCkgPT0gLTEpewoJCQloW25vZGVzXSA9IGhbcG9zXSArIDE7CgkJCWFkZEVkZ2UocG9zLCBub2Rlcywgbnh0KTsKCQkJYWRkTm9kZSgpOwoJCX0KCQlwb3MgPSB0b1tmaW5kKHBvcywgbnh0KV07Cgl9CglwYXRbcG9zXSA9IHRydWU7Cn0KCnZvaWQgREZTKGludCB1KXsKCWNsb3Nlc3RbdV0gPSBwYXRbdV0/IDAgOiAxZTk7Cglmb3IoaW50IGUgPSBsYXN0W3VdOyBlICE9IC0xOyBlID0gbnh0W2VdKXsKCQlpbnQgdiA9IHRvW2VdOwoJCURGUyh2KTsKCQlpZihjbG9zZXN0W3ZdICsgMSA8IGNsb3Nlc3RbdV0pewoJCQljbG9zZXN0W3VdID0gY2xvc2VzdFt2XSArIDE7CgkJfQoJfQp9CgppbnQgc29sdmUoKXsKCURGUygwKTsKCW4gPSBzdHJsZW4oYSk7Cgl2ZWN0b3I8aW50PiBwKG5vZGVzKTsKCWlvdGEoYWxsKHApLCAwKTsKCXNvcnQoYWxsKHApLCBbJl0gKGludCBpLCBpbnQgail7CgkJcmV0dXJuIGhbaV0gPiBoW2pdOwoJfSk7Cglmb3IoaW50IHN0YXkgPSAwOyBzdGF5IDwgMjsgc3RheSsrKXsKCQlmb3IoaW50IHN0YXRlID0gMDsgc3RhdGUgPCBub2Rlczsgc3RhdGUrKyl7CgkJCW1lbW9bbl1bc3RhdGVdW3N0YXldID0gc3RhdGU/IGNsb3Nlc3Rbc3RhdGVdIDogMDsKCQl9Cgl9Cglmb3IoaW50IHBvcyA9IG4gLSAxOyBwb3MgPj0gMDsgcG9zLS0peyAvLyBQb3NpY2lvbiBlbiBhCgkJZm9yKGludCBzdGF5ID0gMDsgc3RheSA8IDI7IHN0YXkrKyl7IC8vIFNpIHB1ZWRvIHJlZ3Jlc2FyIGEgbGEgcmFpeiBvIG5vCgkJCWZvcihpbnQgc3RhdGUgOiBwKXsgLy8gRXN0YWRvIGRlbCB0cmllCgkJCQlpbnQgYW5zID0gMWU5OwoJCQkJZm9yKGludCBlID0gbGFzdFtzdGF0ZV0sIGNhbmQ7IGUgIT0gLTE7IGUgPSBueHRbZV0pewoJCQkJCS8vIFJlZW1wbGF6YXIgYVtwb3NdCgkJCQkJY2FuZCA9IChjaFtlXSArICdBJyAhPSBhW3Bvc10pICsgbWVtb1twb3MgKyAxXVt0b1tlXV1bMV07CgkJCQkJaWYoYW5zID4gY2FuZCkgYW5zID0gY2FuZDsKCQkJCQkvLyBCb3JyYXIgbGEgbGV0cmEgY2hbZV0geSBhdmFuemFyIGFsIHNpZ3VpZW50ZSBlc3RhZG8gZGUgdG9kYXMgZm9ybWFzCgkJCQkJY2FuZCA9IDEgKyBtZW1vW3Bvc11bdG9bZV1dWzBdOwoJCQkJCWlmKGFucyA+IGNhbmQpIGFucyA9IGNhbmQ7CgkJCQl9CgkJCQkvLyBSZWluaWNpYXIgZWwgc3RyaW5nIAoJCQkJaWYoc3RheSkgYW5zID0gbWluKGFucywgY2xvc2VzdFtzdGF0ZV0gKyBtZW1vW3Bvc11bMF1bMF0pOwoJCQkJLy8gQm9ycmFyIGFbcG9zXQoJCQkJYW5zID0gbWluKGFucywgMSArIG1lbW9bcG9zICsgMV1bc3RhdGVdWzFdKTsKCQkJCW1lbW9bcG9zXVtzdGF0ZV1bc3RheV0gPSBhbnM7CgkJCX0KCQl9Cgl9CglyZXR1cm4gbWVtb1swXVswXVsxXTsKfQoKaW50IG1haW4oKXsKCWludCB0OwoJcmkodCk7Cgl3aGlsZSh0LS0pewoJCXJpKGwpOwoJCW5vZGVzID0gZWRnZXMgPSAwOwoJCWFkZE5vZGUoKTsKCQlmb3IoaW50IGkgPSAxOyBpIDw9IGw7IGkrKyl7CgkJCXNjYW5mKCIlcyIsIHYpOwoJCQlpbnNlcnQoaSk7CgkJfQoJCXNjYW5mKCIlcyIsIGEpOwoJCXByaW50ZigiJWRcbiIsIHNvbHZlKCkpOwoJfQoJcmV0dXJuIDA7Cn0K

Success #stdin #stdout 0s 4484KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/xVe1hL

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language