Cod sursa(job #1550135)

Utilizator KOzarmOvidiu Badea KOzarm Data 13 decembrie 2015 11:59:57
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int p1=79,p2=83;
int m,n,d=1,h1,h2,i,a1,a2,b1,b2,t,c[1003];
char A[2000003],B[2000003];
int putere(int x)
{
    if(x>0)
    {if(x%2==1)
        return putere(x-1)*d;
    else
        {int y=putere(x/2);return y*y;}}
    else
        return 1;
}
int main()
{
    fin.getline(A,2000003);
    fin.getline(B,2000003);
    m=strlen(A);
    n=strlen(B);
    d=putere(m-1);
    h1=d%p1;
    h2=d%p2;
    if(m>n)
        return 0;
    for(i=0;i<m;i++)
    {
        a1=(a1*d+A[i])%p1;
        a2=(a2*d+A[i])%p2;
        b1=(b1*d+B[i])%p1;
        b2=(b2*d+B[i])%p2;
    }
    for(i=0;i<=n&&t<1000;i++)
    {
        if(a1==b1&&a2==b2)
        {
            t++;
            c[t]=i;
        }
        b1=(b1-B[i]*d+B[i+m]*d)%p1;
        b2=(b2-B[i]*d+B[i+m]*d)%p2;
    }
    fout<<t<<"\n";
    for(i=1;i<=t;i++)
        fout<<c[i]<<" ";
    return 0;
}