Pagini recente » Cod sursa (job #2040083) | Cod sursa (job #832550) | Cod sursa (job #1191092) | Cod sursa (job #453189) | Cod sursa (job #169450)
Cod sursa(job #169450)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;
const int mod1 = 1 << 18;//128213;
const int pp1 = 3;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
char a[maxn];
int n, m;
char c[maxc][maxl];
char h1[mod1] = {0};
vector<unsigned short> l[mod1];
int p1[maxl];
int pow(int a, int b, int mod)
{
int s = 1;
for ( int i = 1; i <= b; ++i )
s *= a,
s = s & (mod - 1);
return s;
}
int j = 1;
void getnr()
{
int hash1 = 0;
for ( int i = 0; i < n; ++i )
hash1 = (hash1 + p1[i] * c[j][i]) & (mod1 - 1);
++h1[ hash1 ];
l[ hash1 ].push_back(j);
}
char t[maxl];
int check(int what, int from, int to)
{
for ( int i = from; i <= to; ++i )
t[i - from] = a[i];
t[to - from + 1] = '\0';
for ( int i = 0, N = l[what].size(); i < N; ++i )
if ( strcmp(c[ l[ what ][i] ], t) == 0 )
return 1;
return 0;
}
int cnt;
int main()
{
fscanf(in, "%s", a);
m = strlen(a);
fscanf(in, "%s", c[1]);
n = strlen(c[1]);
for ( int i = 0; i < n; ++i )
p1[i] = pow(pp1, n - i - 1, mod1),
getnr();
++j;
while ( fscanf(in, "%s", c[j]) == 1 )
getnr(), ++j;
int hash1 = 0;
for ( int i = 0; i < n; ++i )
hash1 = (hash1 + p1[i] * a[i]) & (mod1 - 1);
if ( h1[ hash1 ] )
if ( check(hash1, 0, n - 1) )
++cnt;
int P1 = p1[0];
for ( int i = n; i < m; ++i )
{
hash1 = ((hash1 - ((a[i - n] * P1) & (mod1 - 1)) + mod1) * pp1 + a[i]) & (mod1 - 1);
if ( h1[ hash1 ] )
if ( check(hash1, i - n + 1, i) )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}