Pagini recente » Cod sursa (job #1078) | Cod sursa (job #60276) | Cod sursa (job #2761628) | Cod sursa (job #105180) | Cod sursa (job #1838738)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 10000002
#define LMAX 22
#define MOD 666013
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector <unsigned int> Hash[MOD + 1];
char s[NMAX], aux[LMAX];
unsigned int p3[LMAX];
int lg, LG;
inline int Number(char x) {
return x - 'a';
}
inline unsigned int Key(unsigned int x) {
return x % MOD;
}
void InsertValue(unsigned int x) {
Hash[Key(x)].push_back(x);
}
bool FindValue(unsigned int x) {
vector <unsigned int> :: iterator it;
unsigned int k = Key(x);
for (it = Hash[k].begin(); it != Hash[k].end(); ++it)
if (*it == x)
return 1;
return 0;
}
// codificam in baza 3
unsigned int GetCode() {
unsigned int ret = 0;
for (int i = 0, j = lg; i <= lg; ++i, --j)
ret = ret + Number(aux[i]) * p3[j];
return ret;
}
int main() {
fin >> s;
LG = strlen(s) - 1;
fin >> aux;
lg = strlen(aux) - 1;
p3[0] = 1;
for (int i = 1; i <= 20; ++i)
p3[i] = 3 * p3[i - 1];
// hash-uim cuvintele din dictionar ca numere in baza 3
do {
unsigned int x = GetCode();
if (!FindValue(x))
InsertValue(x);
}while (fin >> aux);
unsigned int T = 0;
for (int i = 0, j = lg; i <= lg; ++i, --j)
T = T + 1LL * Number(s[i]) * p3[j];
int rez = FindValue(T);
//facem rolling-hash pe sirul mare
for (int i = lg + 1, j = 0; i <= LG; ++i, ++j)n{
T = T - 1LL * Number(s[j]) * p3[lg];
T = T * 3 + Number (s[i]);
rez += FindValue(T);
}
fout << rez;
return 0;
}