Cod sursa(job #1518077)

Utilizator Tomi98Osvath Tamas Tomi98 Data 5 noiembrie 2015 13:19:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <cstring>
#include <iostream>
#define mod1 666013
#define mod2 100019

using namespace std;

string s, p;
int lenP, lenS, P1, P2, num1, num2, aux1, aux2, rez;
int S[1005];

int main()
{

    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");

    getline(fi, p);
    getline(fi, s);

    lenP = int( p.size() );
    lenS = int( s.size() );

    if (lenP > lenS)
    {
        fo << 0 << "\n";
        return 0;
    }

    num1 = num2 = 0;
    P1 = P2 = 1;

    for (int i = 0; i < lenP; i++)
    {

        num1 = (num1 * 26 + p[i]) % mod1;
        num2 = (num2 * 27 + p[i]) % mod2;

        if (i > 0)
        {
            P1 = (P1 * 26) % mod1;
            P2 = (P2 * 27) % mod2;
        }

    }

    aux1 = aux2 = 0;

    for (int i = 0; i < lenP; i++)
    {
        aux1 = (aux1 * 26 + s[i]) % mod1;
        aux2 = (aux2 * 27 + s[i]) % mod2;
    }

    if (aux1 == num1 && aux2 == num2)
    {
        rez++;
        S[rez] = 0;
    }

    for (int i = lenP; i < lenS; i++)
    {
        aux1 = ((((aux1 - (P1 * s[i - lenP])) % mod1) + mod1) * 26 + s[i]) % mod1;
        aux2 = ((((aux2 - (P2 * s[i - lenP])) % mod2) + mod2) * 27 + s[i]) % mod2;

        if (aux1 == num1 && aux2 == num2)
        {
            rez++;
            if (rez <= 1000)
                S[rez] = i - lenP + 1;
        }
    }

    fo << rez << "\n";
    for (int i = 1; i <= min(1000, rez); i++)
        fo << S[i] << " ";
    fo << "\n";

    fi.close();
    fo.close();

    return 0;
}