NKSEV - Tách từ

Tác giả: ll931110

Ngôn ngữ: C++

#include <cmath>
#include <cstring>
#include <iostream>
#define MOD 1337377
using namespace std;

struct trie
{
	int val;
	int d[26];
} tx[400110];

int n,k,cnt = -1;
char S[300010];
char a[105];
int F[300010];

int create()
{
	cnt++;  tx[cnt].val = 0;
	memset(tx[cnt].d,-1,sizeof(tx[cnt].d));
	return cnt;
}

int main()
{
//	freopen("strings.inp","r",stdin);
//	freopen("strings.out","w",stdout);
	scanf("%s", &S);  n = strlen(S);
	int tmp = create();
	
	scanf("%d", &k);
	for (int i = 0; i < k; i++)
	{
		scanf("%s", &a);
		int s = 0;
		for (int j = 0; j < strlen(a); j++)
		{
			int next = tx[s].d[a[j] - 'a'];
			if (next < 0) 
			{				
				next = create();
				tx[s].d[a[j] - 'a'] = next;
			}
			s = next;
		}
		tx[s].val++;		
	}
	
	memset(F,0,sizeof(F));
	F[n] = 1;
	for (int i = n - 1; i >= 0; i--)	
	{		
		int s = 0,j = i;
		while (j < n)
		{
			s = tx[s].d[S[j] - 'a'];
			if (s < 0) break;
			j++;
			F[i] = (F[i] + tx[s].val * F[j]) % MOD;
		}
	}
	printf("%d\n", F[0]);
}

Download