Pagini recente » Cod sursa (job #3179675) | Cod sursa (job #2792368) | Cod sursa (job #716981) | Cod sursa (job #2230614) | Cod sursa (job #781149)
Cod sursa(job #781149)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define modulo 50021
char S[10000010], ss[50];
unsigned int v[90910];
vector<unsigned int> Hash[modulo];
int Check(unsigned int A, int B)
{
unsigned int aux = A % modulo;
if(find(Hash[aux].begin(), Hash[aux].end(), A) != Hash[aux].end()) return 1;
if(B) Hash[aux].push_back(A);
return 0;
}
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
unsigned int N, M, i, j, aux, sol = 0, X = 0;
S[0] = 'a';
fgets(S + 1, 10000005, stdin);
N = strlen(S) - 2;
fgets(ss, 45, stdin);
M = strlen(ss) - 1;
for(i = 0; i < M; i++)
v[1] = v[1] * 3 + ss[i] - 'a';
Check(v[1], 1);
i = 1;
while(!feof(stdin))
{
i ++;
fgets(ss, 45, stdin);
for(j = 0; j < M; j++)
v[i] = v[i] * 3 + ss[j] - 'a';
Check(v[i], 1);
}
aux = 1;
X = 0;
for(i = 1; i < M; i++)
aux *= 3, X = X * 3 + S[i] - 'a';
for(j = 1; j <= N - M + 1; j++)
{
X = (X - (S[j - 1] - 'a') * aux) * 3 + S[j + M - 1] - 'a';
if(Check(X, 0)) sol ++;
}
printf("%u\n", sol);
return 0;
}