Cod sursa(job #2047394)

Utilizator ARobertAntohi Robert ARobert Data 24 octombrie 2017 19:57:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[2000001],n;

int main()
{
    string a,b;
    int i,la,lb,ha1=0,ha2=0,h1=0,h2=0,p1=1,p2=1;
    fin>>a>>b;
    la=a.length();
    lb=b.length();
    for (i=0;i<la;i++)
        {
            ha1=(ha1*101 + a[i])%17789;
            ha2=(ha2*101 + a[i])%17791;
            if (i!=0)
                p1=(p1*101)%17789,
                p2=(p2*101)%17791;
        }
    for (int i=0;i<la;i++)
        h1=(h1*101+b[i])%17789,
        h2=(h2*101+b[i])%17791;
    if (h1==ha1&&h2==ha2)
        v[0]=1, n++;
    for (int i=la;i <lb; i++)
    {
        h1=((h1-(b[i-la] * p1)% 17789 + 17789)*101 + b[i])%17789;
        h2=((h2-(b[i-la] * p2)% 17791 + 17791)*101 + b[i])%17791;
        if (h1==ha1&& h2==ha2)
            v[i-la+1]=1, n++;
    }
    fout<<n<<'\n';
    n=0;
    for (i=0;i<lb&&n<1000;i++)
        if (v[i])
        n++, fout<<i<<" ";
    fout<<'\n';
    return 0;
}