Pagini recente » Cod sursa (job #760446) | Cod sursa (job #1911116) | Cod sursa (job #677103) | Cod sursa (job #2537617) | Cod sursa (job #2555467)
#include <iostream>
#include <fstream>
#include <string>
#include <bitset>
#include <vector>
#include <cmath>
using namespace std;
typedef long long lint;
lint cv(char c){
return c-'a';
}
const lint c1 = 15241;
vector<lint> ve[c1];
struct roller{
const lint alp = 3;
lint val = 0, rm = 1;
int mv;
void extend(char a){
val = (val*alp)+cv(a);
rm *= alp;
mv = (val%c1);
}
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);
mv = (val%c1);
}
int bser(){
const vector<lint> &v = ve[mv];
if(v.empty()){
return 0;
}
int lg = log2(v.size())+1;
int ps = -1;
for(int i = (1<<lg); i > 0; i >>= 1){
if(ps+i < v.size() && val < v[ps+i]){
ps += i;
}
}
return ps+1;
}
bool chek(){
if(ve[mv].empty()){
return false;
}
int ps = bser();
return ve[mv][ps]==val;
}
void setz(){
vector<lint> &v = ve[mv];
int ps = bser();
if(ps == v.size()){
v.push_back(val);
}else{
if(v[ps] != val){
v.insert(v.begin()+ps+1, val);
}
}
}
};
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string s, q;
void altoire(const string &a){
roller r;
r.extend(a);
r.setz();
}
int n;
int sol = 0;
void rezolvescu(){
roller 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;
}