Pagini recente » Cod sursa (job #805311) | Cod sursa (job #2082125) | Rezultatele filtrării | Cod sursa (job #1576240) | Cod sursa (job #1368332)
#include <fstream>
#include <cstring>
using namespace std;
ifstream is ("abc2.in");
ofstream os ("abc2.out");
struct Node{
int Nr;
Node *son[3];
Node()
{
Nr = 0;
son[0] = son[1] = son[2] = 0;
}
};
Node *Trie = new Node, *Hash = new Node;
char Main[10000001], C[22];
int N, Sol;
void Read();
inline void AddTrie(char *w, Node *X, int depth);
inline bool ExistsHash(char *w, Node *X);
inline void AddHash(char *w, Node *X);
inline int Count(char *w, Node *X);
int main()
{
Read();
for (; is >> C; )
if (ExistsHash(C, Hash) == 0)
{
AddHash(C, Hash);
Sol += Count(C, Trie);
}
os << Sol;
is.close();
os.close();
}
void Read()
{
is >> Main;
is >> C;
N = strlen(C);
int Msize = strlen(Main);
for (int i = 0; i <= Msize-N; ++i)
AddTrie(Main+i, Trie, 0);
AddHash(C, Hash);
Sol += Count(C, Trie);
};
inline int Count(char *w, Node *X)
{
if (*w == 0)
return X->Nr;
if (X->son[*w - 'a'] == 0) return 0;
return Count(w+1, X->son[*w - 'a']);
};
inline void AddHash(char *w, Node *X)
{
if (*w == 0) return;
if (X->son[*w - 'a'] == 0)
X->son[*w - 'a'] = new Node;
AddHash(w+1, X->son[*w - 'a']);
};
inline void AddTrie(char *w, Node *X, int depth)
{
if (depth >= N || *w == 0)
{
X->Nr++;
return;
}
if (X->son[*w - 'a'] == 0)
X->son[*w - 'a'] = new Node;
AddTrie(w+1, X->son[*w - 'a'], depth+1);
};
inline bool ExistsHash(char *w, Node *X)
{
if (*w == 0)
return 1;
if (X->son[*w - 'a'] == 0)
return 0;
return ExistsHash(w+1, X->son[*w - 'a']);
};