Pagini recente » Cod sursa (job #1876192) | Cod sursa (job #1422943) | Cod sursa (job #908964) | Cod sursa (job #1957976) | Cod sursa (job #1005041)
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_L = 105;
const int SIGMA = 26;
struct Trie {
int a, b, l;
Trie *sons[SIGMA];
Trie() {
for(int i = 0; i < SIGMA; ++i)
sons[i] = NULL;
a = b = l = 0;
}
};
int Na, Nb, sol;
char S[MAX_L], A[MAX_L];
Trie *root = new Trie;
inline void insert(Trie *node, char S[], int beg, int end, char M, int ind) {
for(int i = beg; i <= end; ++i) {
int next = S[i] - 'a';
if(node->sons[next] == NULL)
node->sons[next] = new Trie;
node = node->sons[next];
if(node->l != ind) {
node->l = ind;
if(M == 'A')
++node->a;
else ++node->b;
}
}
}
inline void DFS(Trie *node) {
if(node->a == Na && node->b == 0)
++sol;
for(int i = 0; i < SIGMA; ++i)
if(node->sons[i] != NULL)
DFS(node->sons[i]);
}
int main() {
ifstream f("sub.in");
ofstream g("sub.out");
f >> Na;
for(int q = 1; q <= Na; ++q) {
f >> S;
int len = strlen(S);
if(S[len-1] == '\n')
--len;
for(int i = 0; i < len; ++i)
insert(root, S, i, len-1, 'A', q);
}
f >> Nb;
for(int q = 1; q <= Nb; ++q) {
f >> S;
int len = strlen(S);
if(S[len-1] == '\n')
--len;
for(int i = 0; i < len; ++i)
insert(root, S, i, len-1, 'B', -q);
}
DFS(root);
g << sol << "\n";
f.close();
g.close();
return 0;
}