Pagini recente » Borderou de evaluare (job #960076) | Borderou de evaluare (job #2223557) | Cod sursa (job #1974674) | Cod sursa (job #2771701) | Cod sursa (job #2515012)
#include <fstream>
#include <cstring>
#include <vector>
#define LMAX 10000005
#define LLMAX 25
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
struct Hash{
long long n, m, power, hashh;
void init(char *s, long long len){
power = 1;
hashh = 0;
for(long long i=len-1; i>=0; i--){
hashh = (hashh + (1LL*power*s[i])%m)%m;
if(i) power = (power*n)%m;
}
}
void roll(char toRemove, char toAdd)
{
hashh=(((hashh-(1LL*toRemove*power)%m+m)*n)%m+toAdd)%m;
}
};
char s[LMAX];
int n;
char cuv[LLMAX];
int m;
int nr=0;
int fr1[40105];
int main()
{
f.getline(s, LMAX);
n=strlen(s);
Hash h1{31, 40099};
while(f>>cuv){
m = strlen(cuv);
h1.init(cuv, m);
fr1[h1.hashh]=1;
}
int nr=0;
h1.init(s, m);
if(fr1[h1.hashh] == 1)
nr++;
//g<<nr;
for(int i = m; i<n; i++){
h1.roll(s[i-m],s[i]);
if(fr1[h1.hashh] == 1)
nr++;
}
g<<nr;
return 0;
}