Cod sursa(job #1282440)

Utilizator sherban26FMI Mateescu Serban-Corneliu sherban26 Data 4 decembrie 2014 10:57:40
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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);

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

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

        p1 = (p1 * PR) % MOD1;
        p2 = (p2 * PR) % MOD2;
    }

    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] - 'a')) % MOD1;
        hq2 = (((hq2 - p2 * sir[i - lss] + MOD2) % MOD2) * PR + (sir[i] - 'a')) % MOD2;

        if (h1 == hq1 && h2 == hq2)
        {
            n++;
            rez.push(i);
        }
    }

    cout << n << "\n";

    i = 1000;
    while (i && !rez.empty())
    {
        cout << rez.front() << " ";
        rez.pop();
    }

    return 0;
}