NKSEV - Tách từ

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int N = 300005;
const int MOD = 1337377;
using namespace std;
char s[N], aa[111];
int f[N];
int n;

struct node {
    int a[26]; int e;
    int& operator[] (int i) {return a[i];}
    node() {for(int i=0; i<26; i++) a[i] = 0; e = 0;}
};

vector<node> a;

void Add(char *s) {
    int pos = 0, i, c;
    for(i=0; c = s[i]; i++) {
        if (a[pos][c - 'a'] == 0) {
            a.push_back(node());
            a[pos][c - 'a'] = a.size() - 1;
        }
        pos = a[pos][c - 'a'];
    }
    a[pos].e = 1;
}

int main()
{
    gets(s); scanf("%d\n", &n);
    int i, j, pos, c;
    a.push_back(node());
    for(i=1;i<=n; i++) {
        gets(aa); Add(aa);
    }
    f[0] = 1;
    for(i=0; s[i]; i++) {
        pos = 0;
        for(j=i; c = s[j]; j++) {
            if (a[pos][c - 'a'] == 0) break;
            pos = a[pos][c - 'a'];
            if (a[pos].e == 1) f[j+1] = (f[j+1] + f[i]) % MOD;
        }
    }
    printf("%d\n", f[strlen(s)]);
    return 0;
}

Download