Cod sursa(job #98595)

Utilizator mariusdrgdragus marius mariusdrg Data 10 noiembrie 2007 14:58:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 3.48 kb
#include<stdio.h>

#include<vector>

#define vpi vector <pair <int,int> >
#define vpii vector <pair <int,int> > :: iterator
#define mkp make_pair
#define ss second
#define pb push_back
#include<algorithm>
const int maxl = 30;
const int maxalf = 30;
const int maxn = 500100;
const int lemax = 10000100;


using namespace std;

//int aut[maxn][maxalf];
int trie[maxn][maxalf];
//char sir[maxn][maxl];
char a[lemax];
int i;
char s[maxl];
int k;
int j;
//int tata[maxn];
//int tatam[maxn];
int nst;
//int niv[maxn];
vpi vect;
int lung;
//int ac[maxn];
bool ver;
//bool stt[maxn];
int m;


bool lit(char a)
{
        return a >= 'a' && a <= 'z';
}

/*
void dfs(int i,int l)
{
        int j;
        
        if (l == lung)
        {
        for(j = 1;j <= m; ++j)
        {
                int k = 1;
                ver = 1;
                for(k = 0;k < lung; ++k)
                {
                        if (sir[j][k] - 'a' != ac[k])
                        {
                                ver = 0;
                                break;
                        }
                }
                if (ver == 1)  break;
        }
        if (ver)
        {
                stt[i] = 1;
        }
        return ;
        }
        for(j = 0;j <= 25; ++j)
        {
                ac[l + 1] = j;
                if (trie[i][j])dfs(trie[i][j], l + 1);
        }
} */

int main()
{
        freopen("abc2.in","r",stdin);
        freopen("abc2.out","w",stdout);
        fgets(a,lemax,stdin);
        int n = strlen(a) - 2;
        int cur;
        nst = 1;
//        printf("%d\n",sizeof(trie));
        while(!feof(stdin))
        {
                ++m;
                fgets(s,30,stdin);
//                memcpy(sir[m],s,sizeof(s));
                lung = strlen(s) - 1;
                while(!lit(s[lung]))
                {
                        --lung;
                }
                cur = 1;
                for(i = 0;i <= lung;++i)
                {
                        if (!trie[cur][s[i] - 'a'])
                        {
                                ++nst;
                                trie[cur][s[i] - 'a'] = nst;
                                /*tata[nst] = cur;
                                tatam[nst] = s[i] - 'a';
                                niv[nst] = niv[cur] + 1;
                                vect.pb(mkp(niv[nst],nst) );  */
                        }
                        cur = trie[cur][s[i] - 'a'];
                }
        }

  /*      sort(vect.begin(),vect.end());
        
        for(i = 0;i <= 26; ++i)
        {
                aut[1][i] = 1;
        }
        for(vpii it = vect.begin(); it != vect.end(); ++it)
        {
                int st = (*it).ss;
                int ant = aut[tata[st]][tatam[st]];
                memcpy(aut[st],aut[ant],sizeof(aut[ant]));
                if (niv[tata[st]] == niv[ant])
                {
                        for(j = 0;j <= 26; ++j)
                        {
                                if (trie[ant][j]) aut[st][j] = trie[ant][j];
                        }
                }
                aut[tata[st]][tatam[st]] = st;
        }

        dfs(1,-1);*/
        int st = 1;
        int ans = 0;

        for(i = lung;i <= n; ++i)
        {
                st = 1;
                for(j = i - lung;j <= i + 1; ++j)
                {
                        if (!trie[st][a[j] - 'a']) break;
                        st = trie[st][a[j] - 'a'];
                }
                if (j == i + 1) ++ans;
        }

        printf("%d",ans);

        return 0;
}