Pagini recente » Cod sursa (job #30919) | Cod sursa (job #467282) | Cod sursa (job #18626) | Cod sursa (job #2304102) | Cod sursa (job #2555371)
#include <iostream>
#include <fstream>
#include <string>
#include <bitset>
#include <vector>
using namespace std;
int cv(char c){
return c-'a';
}
const int c1 = 500041;
const int c2 = 800441;
bitset<c1> bi;
bitset<c2> wi;
struct roller{
const int modit, alp = 3;
int val = 0, rm = 1;
roller(int modit) : modit(modit){}
void extend(char a){
val = ((val*alp)+cv(a)) % modit;
rm = (rm*alp) % modit;
}
void extend(const string &s){
for(auto c : s){
extend(c);
}
}
void roll(char a, char b){
val = (val*alp) - rm*cv(a) + cv(b);
val = (val+modit*100) % modit;
}
};
struct broller{
vector<roller> rol = {roller(c1), roller(c2)};
void extend(char a){
rol[0].extend(a);
rol[1].extend(a);
}
void extend(const string &s){
rol[0].extend(s);
rol[1].extend(s);
}
void roll(char a, char b){
rol[0].roll(a, b);
rol[1].roll(a, b);
}
void setz(){
bi[rol[0].val] = true;
wi[rol[1].val] = true;
}
bool chek(){
return bi[rol[0].val]&&wi[rol[1].val];
}
};
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string s, q;
void altoire(const string &a){
broller r;
r.extend(a);
r.setz();
}
int n;
int sol = 0;
void rezolvescu(){
broller r;
for(int i = 0; i < n; ++i){
r.extend(s[i]);
}
if(r.chek()){
sol++;
}
for(int i = n; i < s.size(); ++i){
r.roll(s[i-n], s[i]);
if(r.chek()){
sol++;
}
}
fout << sol;
}
int main(){
ios_base::sync_with_stdio(false);
fin >> s;
while(fin >> q){
n = q.size();
altoire(q);
}
rezolvescu();
return 0;
}