Cod sursa(job #2122639)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 5 februarie 2018 12:58:13
Problema Potrivirea sirurilor Scor 96
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <string.h>

#define MOD 666013

using namespace std;

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

int n1,n2,val1,val2,put1,lg,sol[2000005];
const int baza=53;
char a[2000005],b[2000005];

bool ver(int x)
{
    int i,lung;
    lung=n1;
    for(i=x;i>=x-n1+1;i--)
        {
            if(b[i]!=a[lung])
                return 0;
            lung--;
        }
    return 1;
}
int main()
{
    fin>>(a+1)>>(b+1);
    int i,putere=1;
    n1=strlen(a+1);
    n2=strlen(b+1);
    lg=1;
    for(i=n1;i>=1;i--)
    {
        if(i==1)
            put1=putere;
        val1+=((a[i]-64)*putere)%MOD; ///(int)
        val1%=MOD;
        putere*=baza;
        putere%=MOD;
    }
    putere=1;
    for(i=n1;i>=1;i--)
    {
        val2+=((b[i]-64)*putere)%MOD;
        val2%=MOD;
        putere*=baza;
        putere%=MOD;
    }
    if(val1==val2)
    {
        if(ver(n1)==1)
        {
            sol[lg]=0;
            lg++;
        }
    }

    for(i=n1+1;i<=n2;i++)
    {
        val2=val2-((b[i-n1]-64)*put1)%MOD;
        if(val2<0)
            val2+=MOD;
        val2=val2*baza;
        val2+=b[i]-64;
        val2%=MOD;
        if(val1==val2)
        {
            if(ver(i)==1)
            {
                sol[lg]=i-n1;
                lg++;
            }
        }
    }
    lg--;
    fout << lg << '\n';

    if(lg>1000)
        lg=1000;

    for(i=1;i<=lg;i++)
        fout << sol[i] << ' ';
    fout << '\n';
    return 0;
}