Pagini recente » Cod sursa (job #492066) | Cod sursa (job #353147) | Cod sursa (job #1567152) | Cod sursa (job #1105364) | Cod sursa (job #201618)
Cod sursa(job #201618)
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;
const int NMAX=10000002,NrMax=50001;
int L,n,sol,i,m;
unsigned word[NrMax],x,p;
string t,s;
ifstream f("abc2.in");
ofstream g("abc2.out");
int gasit(unsigned int x){
int ls=1,ld=m,mij;
while (ls<=ld) {
mij=(ls+ld)/2;
if (word[mij]==x) return 1;
if (word[mij]<x) ls=mij+1;
else ld=mij-1;
}
return 0;
}
int main(){
getline(f,t);
L=t.size();
while (getline(f,s)){
n=s.size();
for (i=x=0,p=1;i<n;++i,p*=3)
x+=(s[i]-'a')*p;
word[++m]=x;
}
sort(word+1,word+m+1);
for (i=x=0,p=1;i<n;++i,p*=3)
x+=(t[i]-'a')*p;
p/=3;
if (gasit(x)) sol=1;
for (i=n;i<L;++i){
x=(x-t[i-n]+'a')/3+(t[i]-'a')*p;
if (gasit(x)) ++sol;
}
g<<sol;
return 0;
}