Cod sursa(job #912592)

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

#define mod 666013

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

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

int main (){
    int i,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,ler=1;i<m;++i,ler*=52,ler%=mod){
        crt+=nr(b[i])*ler;
        crt%=mod;
        t+=nr(a[i])*ler;
        t%=mod;
    }
    if(crt==t)rez[++dim]=0;
    for(i=m;i<n;++i){
        crt=((crt%p)*52+nr(b[i]))%mod;
        //g<<crt<<'\n';
        if(crt==t){
            ++dim;
            if(dim<=1000)rez[dim]=i;
        }
    }
    g<<dim<<'\n';
    for(i=1;i<=min(dim,1000);++i)g<<rez[i]-2<<' ';
    return 0;
}