Pagini recente » Cod sursa (job #1416986) | Cod sursa (job #2961682) | Cod sursa (job #1751823) | Cod sursa (job #3187274) | Cod sursa (job #530463)
Cod sursa(job #530463)
#include <fstream>
#include <vector>
using namespace std;
struct Trie
{
int pos;
Trie* son[3];
Trie()
{
pos = 0;
son[0] = son[1] = son[2] = 0;
}
};
Trie* T = new Trie;
void getIn(Trie* now, char* C, int deep)
{
++now->pos;
if (*C == '\0' || deep > 20)
return;
if (now->son[*C - 'a'] == 0)
{
Trie* noda = new Trie;
now->son[*C - 'a'] = noda;
}
getIn(now->son[*C - 'a'], C + 1, deep + 1);
}
int getPos(Trie* now, char* C)
{
if (*C == '\0') return now->pos;
if (now->son[*C - 'a'] == 0) return 0;
return getPos(now->son[*C - 'a'], C + 1);
}
const int MOD = 3033;
vector<unsigned int> Hash[MOD];
void AddH(unsigned int value)
{
int pos = value % MOD;
for (vector<unsigned int>::iterator it = Hash[pos].begin(); it != Hash[pos].end(); ++it)
if (*it == value)
return;
Hash[pos].push_back(value);
}
bool Find(unsigned int value)
{
int pos = value % MOD;
for (vector<unsigned int>::iterator it = Hash[pos].begin(); it != Hash[pos].end(); ++it)
if (*it == value)
return true;
return false;
}
char text[10000002];
char query[22];
long long result;
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin.getline(text, sizeof(text));
for (int i = 0; text[i] != '\0'; ++i)
getIn(T, text + i, 1);
while (fin.getline(query, sizeof(query)))
{
unsigned int now = 0, pow3 = 0;
for (int i = 0; query[i] != '\0'; ++i)
{
pow3 = (pow3 == 0 ? 1 : pow3 * 3);
now += pow3 * (query[i] - 'a');
}
bool found = Find(now);
if (!found)
{
AddH(now);
result += getPos(T, query);
}
}
fout << result;
fin.close();
fout.close();
}