Pagini recente » Cod sursa (job #1513550) | Cod sursa (job #2953550) | Cod sursa (job #1172485) | Cod sursa (job #2034722) | Cod sursa (job #512312)
Cod sursa(job #512312)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 10000005;
const int B1 = 3;
const int P1 = 666013;
char s[N], t[50001][25];
typedef unsigned int ui;
ui n, a, b, m;
vector<ui> x[P1 + 10];
int main() {
ifstream fin("abc2.in");
ofstream fout("abc2.out");
ui i, r, nr = 0, val1 = 1, val2 = 1, j;
fin.getline(s,N);
while( !fin.eof()) {
++n;
fin.getline(t[n],25);
}
--n;
val1 = 1;
r = strlen(t[1]);
for(i = 1 ; i < r; ++i) {
val1 = (val1 * B1) % P1;
val2 = val2 * B1;
}
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 * B1 +t[i][j] -'a' + 1;
x[a].push_back(b);
}
a = 0;
b = 0;
for( i = 0; i < r; ++i) {
a = ( a * B1 + s[i] - 'a' + 1) % P1;
b = ( b * B1 + s[i] - 'a' + 1);
}
m = strlen(s);
s[m] = 'a';
for( i = r; i <= m ; ++i) {
for( j = 0; j < x[a].size(); ++j)
if(x[a][j] == b) {
++nr;
break;
}
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); b = (b * B1 + s[i] - 'a' + 1);
}
fout<<nr<<'\n';
fin.close();
fout.close();
return 0;
}