NKSEV - Tách từ

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>

using namespace std;

struct Trie {
	bool last;
	Trie * n[26];
};

Trie container[800000];
int ncon;

int n, N;
char a[300030], tmp[444];
Trie root;
int f[300030];
const int mod = 1337377;

void add( char * a) {
	Trie * p = &root;
	for(int i=0;a[i]!=0;++i) {
		int t = a[i] - 'a';
		if(p->n[t]!=NULL) p = p->n[t];
		else {
			p->n[t] = container + ++ncon;
			p = p->n[t];
		}
	}
	p->last = true;
}

int main() {
	gets(a);
	n = strlen(a);
	scanf("%d", &N);
	gets(tmp);
	for(int i=0;i<N;++i) {
		gets(tmp);
		add( tmp);
	}
	f[n] = 1;
	for(int i=n-1;i>=0;--i) {
		Trie * p = &root;
		for(int j=i;j<n;++j) {
			int t = a[j] - 'a';
			if(p->n[t]==NULL) break;
			p = p->n[t];
			if(p->last) f[i] += f[j+1];
		}
		f[i] %= mod;
	}
	cout << f[0] << endl;
	//system("pause");
	return 0;
}

Download