Cod sursa(job #201618)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 1 august 2008 20:50:05
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#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;
}