Pagini recente » Cod sursa (job #949866) | Cod sursa (job #41304) | Cod sursa (job #663120) | Cod sursa (job #995276) | Cod sursa (job #2605725)
#include <stdio.h>
#include <stdlib.h>
int n, m;
typedef struct TrieStruct{
int wordsContained;
int lastWord;
struct TrieStruct *next[27];
}Trie;
void add_trie(Trie *crtNode, char *word, int wordIndex, int type){
if(crtNode->lastWord != wordIndex){
crtNode->wordsContained ++;
crtNode->lastWord = wordIndex;
}
if(*word == 0){
return;
}
int nextIndex = *word - 'a';
if(crtNode->next[nextIndex] == NULL){
if(type == 0)
crtNode->next[nextIndex] = calloc(1, sizeof(Trie));
else
return;
}
add_trie(crtNode->next[nextIndex], word + 1, wordIndex, type);
}
void reset(Trie *crtNode, char *word){
crtNode->wordsContained = 0;
if(*word == 0){
return;
}
int nextIndex = *word - 'a';
if(crtNode->next[nextIndex] != NULL)
reset(crtNode->next[nextIndex], word + 1);
}
int dfs(Trie *crtNode){
int sum = 0;
for(int i = 0; i < 27; ++ i){
if(crtNode->next[i] != NULL){
if(crtNode->next[i]->wordsContained == n)
sum = sum + 1 + dfs(crtNode->next[i]);
else
sum = sum + dfs(crtNode->next[i]);
}
}
return sum;
}
int main()
{
FILE *in = fopen("sub.in", "r");
FILE *out = fopen("sub.out", "w");
Trie *trie = calloc(1, sizeof(Trie));
char word[400] = {};
fscanf(in, "%d", &n);
for(int i = 1; i <= n; ++ i){
fscanf(in, "%s", &word);
int cnt = 0;
while(word[cnt] != 0){
if(i == 1)
add_trie(trie, word + cnt, i, 0);
else
add_trie(trie, word + cnt, i, 1);
cnt ++;
}
}
fscanf(in, "%d", &m);
for(int i = 1; i <= m; ++ i){
fscanf(in, "%s", &word);
int cnt = 0;
while(word[cnt] != 0){
reset(trie, word + cnt);
cnt ++;
}
}
fprintf(out, "%d", dfs(trie));
return 0;
}