Cod sursa(job #2284487)

Utilizator AndoneAlexandruAndone Alexandru AndoneAlexandru Data 17 noiembrie 2018 11:13:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

long long int n1 = 31, m1 = 40099;
long long int n2 = 53, m2 = 319993;
long long int h1, h2, h3, h4;

int nr;
int indici[999999];

char c[2000005];
char s[2000005];

int main()
{
    f.getline(c, 2000005);
    f.getline(s, 2000005);

    int k1 = strlen(c);
    int k2 = strlen(s);
    long long int putere1 = 1;
    long long int putere2 = 1;

    for (int i = k1-1; i >= 0; i--)
    {
        h1 = (h1 + c[i]*putere1)%m1;
        h3 = (h3 + s[i]*putere1)%m1;
        if (i > 0) putere1 = (putere1*n1)%m1;
        h2 = (h2 + c[i]*putere2)%m2;
        h4 = (h4 + s[i]*putere2)%m2;
        if (i > 0) putere2 = (putere2*n2)%m2;
    }

    for (int i = k1; i < k2+1; i++)
    {
        if (h1 == h3 && h2 == h4)
        {
            if (nr > 1000)
                nr++;
            else indici[nr++] = i-k1;
        }
        h3 = ((h3 - (s[i-k1]*putere1) % m1 + m1)*n1+s[i])%m1;
        h4 = ((h4 - (s[i-k1]*putere2) % m2 + m2)*n2+s[i])%m2;
    }

    g << nr << "\n";
    if (nr > 1000)
        nr = 1000;
    for (int i = 0; i < nr; i++)
        g << indici[i] << " ";
    return 0;
}