Pagini recente » Cod sursa (job #2704199) | Cod sursa (job #3121865) | Cod sursa (job #687441) | Cod sursa (job #714335) | Cod sursa (job #108401)
Cod sursa(job #108401)
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
struct node
{
node *f[3], *next[3];
vector<node *> R;
int d;
bool end;
};
void add(node **nod, char *s, int h);
void go(node *nod, node *T, char u);
char S[10000001];
int N;
node *root, *X;
int main()
{
char s[32];
int nr = 0;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(S, 10000001, stdin);
while(!feof(stdin))
{
scanf("%s ", s);
add(&root, s, 0);
}
go(root, 0, 'a');
X = root;
S[strlen(S) - 1] = 0;
N = strlen(S);
for(int i = 0; i < N; i++)
{
X = X->next[S[i] - 'a'];
if(X->end)
nr++;
}
printf("%d\n", nr);
return 0;
}
void add(node **nod, char *s, int h)
{
if((*nod) == 0)
{
*nod = new node;
(*nod)->f[0] = (*nod)->f[1] = (*nod)->f[2] = 0;
(*nod)->d = h;
if(s[0] == 0) (*nod)->end = true;
else
(*nod)->end = false, add(&((*nod)->f[s[0] - 'a']), s + 1, h + 1);
}
else
{
if(s[0] == 0)(*nod)->end = true;
else
(*nod)->end = false, add(&((*nod)->f[s[0] - 'a']), s + 1, h + 1);
}
}
void go(node *nod, node *T, char u)
{
int i, j;
nod->R.push_back(root);
if(T)
{
for(i = 0; i < (T->R).size(); i++)
if(T->R[i]->f[u - 'a'])
nod->R.push_back(T->R[i]->f[u - 'a']);
else;
}
for(j = 0; j < 3; j++)
{
nod->next[j] = root;
if(nod->f[j])
{
nod->next[j] = nod->f[j];
continue;
}
for(i = nod->R.size() - 1; i >= 0; i--)
if(nod->R[i]->f[j] != 0)
{
nod->next[j] = nod->R[i]->f[j];
break;
}
}
for(j = 0; j < 3; j++)
if(nod->f[j])
go(nod->f[j], nod, j + 'a');
}