Pagini recente » Cod sursa (job #2563042) | Cod sursa (job #3143064) | Cod sursa (job #1188847) | Cod sursa (job #1164015) | Cod sursa (job #1330639)
/// sub
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <string>
#define ch(a) ((int)((a)-'a'))
using namespace std;
struct trie {
trie *son[26];
int last;
int cnt;
bool valid;
trie() {
cnt = 0;
last = 0;
valid = true;
for (int i=0;i<26;i++) {
son[i] = NULL;
}
}
~trie() {
cnt = 0;
last = 0;
valid = false;
for (int i=0;i<26;i++) {
delete son[i];
son[i] = NULL;
}
}
};
ifstream f("sub.in");
ofstream g("sub.out");
struct trie *root, *node;
int n, m;
string in;
int len;
void addTrieA(int index) {
for (int i=0;i<len;i++) {
node = root;
for (int j=i;j<len;j++) {
int p = ch(in[j]);
if (node->son[p] == NULL)
node->son[p] = new trie();
if (node->son[p]->valid)
node = node->son[p];
else
break;
if (node->last < index) {
node->last = index;
node->cnt++;
}
}
}
}
void markB() {
for (int i=0;i<len;i++) {
node = root;
for (int j=i;j<len;j++) {
int p = ch(in[j]);
if (node->son[p] != NULL) {
node->son[p]->valid = false;
node = node->son[p];
} else
break;
}
}
}
int countTrie(trie *aux) {
int answ = 0;
if (aux->cnt == n && aux->valid) answ = 1;
for (int i=0;i<26;i++)
if (aux->son[i] != NULL)
answ += countTrie(aux->son[i]);
return answ;
}
void read() {
root = new trie();
f>>n;
for (int i=1;i<=n;i++) {
f>>in;
len = in.size();
addTrieA(i);
}
f>>m;
for (int i=1;i<=m;i++) {
f>>in;
len = in.size();
markB();
}
g<<countTrie(root)<<'\n';
}
int main() {
read();
f.close(); g.close();
return 0;
}