Cod sursa(job #1148852)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 21 martie 2014 10:36:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>
#define mod1 123456
#define mod2 145678

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char c[2000010],x[2000010];
int n1,n2,putere1,putere2,nr1,nr2,nrc1,nrc2,i,nr;
bool f[2000010];


int main () {

    fin>>c;
    fin>>x;
    n1=strlen (c);
    n2=strlen (x);
    if (c>x) {
        fout<<"0\n";
        return 0;
    }
    putere1=putere2=1;
    for (i=0;i<n1;i++) {
        nr1=(nr1*26 + c[i]-'A')%mod1;
        nr2=(nr2*26 + c[i]-'A')%mod2;
        if (i!=0) {
            putere1=(putere1*26)%mod1;
            putere2=(putere2*26)%mod2;
        }
    }
    for (i=0;i<n1;i++) {
        nrc1=(nrc1*26 + x[i]-'A')%mod1;
        nrc2=(nrc2*26 + x[i]-'A')%mod2;
    }

    if (nrc1==nr1&&nrc2==nr2) {
        f[0]=1;
        nr++;
    }
    for (i=n1;i<n2;i++) {
        nrc1=((nrc1-((x[i-n1]-'A')*putere1)%mod1+mod1)*26+(x[i]-'A'))%mod1;
        nrc2=((nrc2-((x[i-n1]-'A')*putere2)%mod2+mod2)*26+(x[i]-'A'))%mod2;
        if (nrc1==nr1&&nrc2==nr2) {
            f[i-n1+1]=1;
            nr++;
        }
    }

    fout<<nr<<"\n";
    if (nr>1000)
            nr=1000;
    for (i=0;nr;i++) {
        if (f[i]==1) {
            fout<<i<<" ";
            nr--;
        }
    }


    return 0;
}