Pagini recente » Cod sursa (job #3127802) | Cod sursa (job #227267) | Cod sursa (job #2802388) | Cod sursa (job #1150515) | Cod sursa (job #512026)
Cod sursa(job #512026)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 10000005;
const int B1 = 3;
const int B2 = 5;
const int P1 = 1024 * 128;
const int P2 = 1000007;
char s[N], t[50001][25],x[P1],y[P2];
int n, a, b, m;
int min( int a, int b ) {
return a<b?(a):(b);
}
int main() {
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int i, r, nr = 0, val1, val2, j;
fin.getline(s,N);
while( !fin.eof()) {
++n;
fin.getline(t[n],25);
// fout<<t[n]<<'\n';
}
--n;
val1 = 1;
val2 = 1;
r = strlen(t[1]);
for(i = 1 ; i < r; ++i){
val1 = (val1 * B1) % P1;
val2 = (val2 * B2) % P2;
}
for( i = 1; i <= n; ++i) {
a = b = 0;
for( j = 0; j < r; ++j) {
a = ( a * B1 + t[i][j] - 'a' + 1) % P1;
b = ( b * B2 + t[i][j] - 'a' + 1) % P2;
}
x[a] = 1;y[b] = 1;
// fout<<a<<" "<<b<<'\n';
}
a = 0;
b = 0;
// fout<<val1<<" "<<val2<<" "<<B1<<" "<<B2<<" "<<P1<<" "<<P2<<'\n';
for( i = 0; i < r; ++i) {
a = ( a * B1 + s[i] - 'a' + 1) % P1;
b = ( b * B2 + s[i] - 'a' + 1) % P2;
}
m = strlen(s);
for( i = r; i <= m ; ++i) {
if( x[a] && y[b])
++nr;
// fout<<a<<" "<<b<<'\n';
a = (a - (s[i - r] - 'a' + 1) * val1 ) % P1 + P1; a = (a * B1 + s[i] - 'a' +1) % P1;
b = (b - (s[i - r] - 'a' + 1) * val2 ) % P2 + P2; b = (b * B2 + s[i] - 'a' +1) % P2;
}
fout<<nr<<'\n';
fin.close();
fout.close();
return 0;
}