Cod sursa(job #975855)

Utilizator cat_red20Vasile Ioana cat_red20 Data 21 iulie 2013 20:19:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include<fstream>
#include<string>
#define MAXL 2000002
#define MOD 666013
#define MOD2 100003
#define BASE 101
using namespace std;
int pow[MAXL],pow2[MAXL],l1,l2,sol[1001],nrsol,valA1,valA2,valB1,valB2;
string s1,s2;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
void citire()
{
    fin>>s1>>s2;
    l1=s1.length();
    l2=s2.length();
}

void puteri()
{
    pow[0]=1;
    pow2[0]=1;
    for(int i=1;i<=l1;i++)
    {
        pow[i]=(pow[i-1]*BASE)%MOD;
        pow2[i]=(pow2[i-1]*BASE)%MOD2;
    }
}

int transforma(string s,int l)
{
    int p=0;
    for(int i=0;i<=l;i++)
    {
        p+=(s[i]*pow[l-i])%MOD;
        if(p>MOD)
           p-=MOD;
    }
    return p;
}

int transforma2(string s,int l)
{
    int p=0;
    for(int i=0;i<=l;i++)
    {
        p+=(s[i]*pow2[l-i])%MOD2;
        if(p>=MOD2)
        p-=MOD2;
    }
    return p;
}
void adauga(int poz,int &val1,int &val2)
{
    val1-=(pow[l1-1]*s2[poz-l1])%MOD;
    val1=(val1+MOD)%MOD;
    val1=(val1*BASE)%MOD+s2[poz];
    if(val1>MOD)
    val1-=MOD;

    val2-=(pow2[l1-1]*s2[poz-l1])%MOD2;
    val2=(val2+MOD2)%MOD2;
    val2=(val2*BASE)%MOD2+s2[poz];
    if(val2>MOD2)
    val2-=MOD2;
}
void rezolva()
{
    valA1=transforma(s1,l1-1);
    valB1=transforma(s2,l1-1);
    valA2=transforma2(s1,l1-1);
    valB2=transforma2(s2,l1-1);
    for(int i=l1;i<l2;i++)
    {
        if(valA1==valB1 && valA2==valB2)
        {
            nrsol++;
            if(nrsol<=1000)
            sol[nrsol]=i-1;
        }
        adauga(i,valB1,valB2);
    }
    if(valA1==valB1)
    sol[++nrsol]=l2-1;
}


void afisare()
{
    fout<<nrsol<<'\n';
    for(int i=1;i<=nrsol && i<=1000;i++)
    {
        fout<<sol[i]-l1+1<<' ';
    }
}
int main()
{
    citire();
    if(l1>l2)
    {
        fout<<0;
        return 0;
    }
    puteri();
    rezolva();
    afisare();
 return 0;
}