Cod sursa(job #912602)

Utilizator ephgstefana gal ephg Data 12 martie 2013 16:34:06
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<string>
#include<cctype>
using namespace std;

#define mod 666013

int n,m,p=1;
string a,b,s;
int rez[1005],dim;

int nr(char c){
    if(islower(c))return c-'a'+26;
    return c-'A';
}

int main (){
    int i,j,crt=0,ler,t=0;
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    n=b.size();
    m=a.size();
    for(i=1;i<m;++i)p*=52,p%=mod;
    for(i=0;i<m;++i){
        crt=crt*52+nr(b[i]);
        crt%=mod;
        t=t*52+nr(a[i]);
        t%=mod;
    }
   // g<<crt<<' '<<t<<'\n';
    if(crt==t)rez[++dim]=0;
    for(i=1;i<=n-m;++i){
        crt=((crt-(p*nr(b[i-1]))%mod+mod)*52+nr(b[i+m-1]))%mod;
        //g<<crt<<'\n';
        if(crt==t){
            s="";
            for(j=0;j<m;++j)s+=b[i+j];
            if(s==a){
                ++dim;
                if(dim<=1000)rez[dim]=i;
            }
        }
    }
    g<<dim<<'\n';
    for(i=1;i<=min(dim,1000);++i)g<<rez[i]<<' ';
    return 0;
}