Cod sursa(job #1282454)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 4 decembrie 2014 11:20:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <queue>

#define LMAX 2000010
#define PR 97
#define MOD1 1336337
#define MOD2 1333333

using namespace std;

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

char subsir[LMAX], sir[LMAX];
int n, h1, h2, hq1, hq2, p1, p2;
queue <int> rez;

int main()
{
    fin >> subsir >> sir;

    int i, ls = strlen(sir), lss = strlen(subsir);

    if (ls < lss)
    {
        fout << 0;
        return 0;
    }

    p1 = 1; p2 = 1;
    h1 = subsir[0];
    h2 = subsir[0];
    hq1 = sir[0];
    hq2 = sir[0];
    for (i = 1; i < lss; i++)
    {
        h1 = (h1 * PR + subsir[i]) % MOD1;
        h2 = (h2 * PR + subsir[i]) % MOD2;

        hq1 = (hq1 * PR + sir[i]) % MOD1;
        hq2 = (hq2 * PR + sir[i]) % MOD2;

        p1 = (p1 * PR) % MOD1;
        p2 = (p2 * PR) % MOD2;
    }
//cout << h1 << " " << h2 << endl << hq1 << " " << hq2 << endl;
    if (h1 == hq1 && h2 == hq2)
    {
        n = 1;
        rez.push(0);
    }

    for (i = lss; i < ls; i++)
    {
        hq1 = (((hq1 - p1 * sir[i - lss]) % MOD1 + MOD1) * PR + sir[i]) % MOD1;
        hq2 = (((hq2 - p2 * sir[i - lss]) % MOD2 + MOD2) * PR + sir[i]) % MOD2;
//cout << hq1 << " " << hq2 << endl;
        if (h1 == hq1 && h2 == hq2)
        {
            n++;
            rez.push(i - lss + 1);
        }
    }

    n = min(n, 1000);
    fout << n << "\n";

    while (n)
    {
        fout << rez.front() << " ";
        rez.pop();
        n--;
    }

    return 0;
}