Pagini recente » Cod sursa (job #2122019) | Cod sursa (job #178208) | Cod sursa (job #840398) | Cod sursa (job #3196975) | Cod sursa (job #2636784)
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
constexpr int base = 3;
constexpr int MOD = 666013;
constexpr int cuvmax = 5e4 + 5;
unsigned int rest[cuvmax], ultpoz[cuvmax], value[cuvmax];
unsigned int ult[MOD];
unsigned int length, power;
string text;
void Read () {
f >> text;
string cuv;
unsigned int N = 0;
while (f >> cuv) {
int val = 0;
length = cuv.size();
for (int i = 0; i < cuv.size(); ++ i ) {
val = val * base + (cuv[ i ] - 'a');
}
value[ ++ N ] = val;
rest[ N ] = val % MOD;
if (ult[ val % MOD ])
ultpoz[ N ] = ult[ val % MOD ];
ult[ val % MOD ] = N;
}
power = 1;
for (int i = 1; i < length; ++ i ) {
power = power * base;
}
}
bool Verif (unsigned int val) {
for (int i = ult[ val % MOD ]; i != 0; i = ultpoz[ i ]) {
if (val == value[ i ]) return 1;
}
return 0;
}
void Solve () {
unsigned int val = 0;
int sol = 0;
for (int i = 0; i < length; ++ i ) {
val = val * base + (text[ i ] - 'a');
}
if (Verif(val)) ++ sol;
for (int i = length; i < text.size(); ++ i ) {
val = (val - power * (text[ i - length ] - 'a')) * base + (text[ i ] - 'a');
if (Verif(val))
++ sol;
}
g << sol << '\n';
}
int main()
{
Read ();
Solve ();
return 0;
}