Cod sursa(job #1716026)

Utilizator akaprosAna Kapros akapros Data 11 iunie 2016 20:44:17
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 9000002
#define maxL 302
#define sigma 26
using namespace std;
int n, m, tsize = 1, st[maxN], top, ans, k;
char w[maxL];
int ok[maxN];
bool upd;
typedef struct
{
    int c[sigma], p;
    unsigned short val;
    char nc;
} trie;
trie t[maxN];
void insert(char *s)
{
    int ind = 1, C;
    for ( ; *s; ++ s)
    {
        C = *s - 'a';
        if (!t[ind].c[C])
        {
            if (top)
            {
                t[ind].c[C] = st[top];
                -- top;
            }
            else
                t[ind].c[C] = ++ tsize;
            t[t[ind].c[C]].p = ind;
            ++ t[ind].nc;
        }
        ind = t[ind].c[C];
        if (ok[ind] != k)
            ++ t[ind].val;
        if (t[ind].val == n && ok[ind] != k)
            ++ ans;
        ok[ind] = k;
    }
}
void Insert(char *s)
{
    int ind = 1, C;
    for ( ; *s; ++ s)
    {
        C = *s - 'a';
        if (!t[ind].c[C])
        {
            upd = 1;
            return;
        }
        ind = t[ind].c[C];
        if (t[ind].val == n)
            -- ans;
        t[ind].val = -1;
    }
}

void read()
{
    int i, j;
    freopen("sub.in", "r", stdin);
    scanf("%d\n", &n);
    for (i = 1; i <= n; ++ i)
    {
        k = i;
        //memset(ok, 0, sizeof(ok));
        gets(w + 1);
        int len = strlen(w + 1);
        for (j = 1; j <= len; ++ j)
            insert(w + j);
    }
}
void solve()
{
    int i, j;
    scanf("%d\n", &m);
    for (i = 1; i <= m; ++ i)
    {
        gets(w + 1);
        int len = strlen(w + 1);
        for (j = 1; j <= len; ++ j)
        {
            upd = 0;
            Insert(w + j);
            if (!upd)
                break;
        }
    }
}
void write()
{
    freopen("sub.out", "w", stdout);
    printf("%d\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}