Pagini recente » Cod sursa (job #2061109) | Cod sursa (job #1297391) | Cod sursa (job #2274607) | Cod sursa (job #1060802) | Cod sursa (job #265582)
Cod sursa(job #265582)
#include <fstream>
using namespace std;
typedef long long LL;
const LL BASE = 3;
const LL M = 97957LL;//969LL;
const LL M2 = 99987LL;
bool Hash1[100000];
bool Hash2[100000];
char text[10000001];
int check(int X, int Y) {
if (Hash1[X] && Hash2[Y]) return 1;
return 0;
}
int main() {
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> text;
char word[21];
int m = 0;
while (fin >> word) {
LL idx = 0;
LL idx2 = 0 ;
m = 0;
for (int i = 0; word[i]; ++i, ++m) {
idx*=BASE, idx+=(word[i]-'a'), idx%=M;
idx2*=BASE, idx2+=(word[i]-'a'), idx2%=M2;
}
Hash1[idx] = true;
Hash2[idx2] = true;
}
int total = 0;
//adauga
LL number = 0;
LL num2 = 0;
LL BB = 1;
LL BB2 = 1;
for (int i = 1; i < m; ++i) BB*=BASE, BB%=M, BB2*=BASE, BB2%=M2;
for (int i = 0; i < m; ++i) {
number*=BASE, number+=text[i]-'a', number%=M;
num2*=BASE, num2+=text[i]-'a', num2%=M2;
}
total+=check(number, num2);
for (int i = m; text[i]; ++i) {
num2+=M2; num2-=BB2 * (text[i-m]-'a'), num2%=M2;
number+=M; number-=BB * (text[i-m]-'a'); number%=M;
num2*=BASE, num2+=text[i]-'a', num2%=M;
number*=BASE; number+=text[i] - 'a'; number%=M;
total+=check(number, num2);
}
fout << total << '\n';
return 0;
}