Pagini recente » Cod sursa (job #1156624) | Cod sursa (job #2976580) | Cod sursa (job #153362) | Cod sursa (job #2682131) | Cod sursa (job #2515005)
#include <fstream>
#include <cstring>
#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 fr2[319997];
int main()
{
f.getline(s, LMAX);
n=strlen(s);
Hash s1pHash{31, 40099}, s2pHash{31, 40099};
Hash s1oHash{53, 319993}, s2oHash{53, 319993};
while(f.getline(cuv, LLMAX)){
m = strlen(cuv);
s1pHash.init(s, m);
s1oHash.init(s, m);
s2pHash.init(cuv, m);
s2oHash.init(cuv, m);
if(fr1[s2pHash.hashh] == 1 && fr2[s2oHash.hashh]==1)
continue;
fr1[s2pHash.hashh] = 1;
fr2[s2oHash.hashh] = 1;
if(s1pHash.hashh == s2pHash.hashh && s1oHash.hashh == s2oHash.hashh)
nr++;
for(long long i=m; i<n; i++){
s1pHash.roll(s[i-m], s[i]);
s1oHash.roll(s[i-m], s[i]);
if(s1pHash.hashh == s2pHash.hashh && s1oHash.hashh == s2oHash.hashh)
nr++;
}
}
g<<nr;
return 0;
}