Cod sursa(job #1289974)

Utilizator tudi98Cozma Tudor tudi98 Data 10 decembrie 2014 17:39:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
using namespace std;
#define q 101
#define M1 666013
#define M2 10007

vector<int> Sol;

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

    string A,B;
    fin >> A >> B;
    int n = A.size();
    int m = B.size();

    if(n > m)
    {
        fout << "0";
        return 0;
    }

    int Hpat1 = 0, Hpat2 = 0;
    int Hstr1 = 0, Hstr2 = 0;

    for(int i = 0; i < n; i++)
    {
        Hpat1 = (Hpat1 * q + A[i]) % M1;
        Hpat2 = (Hpat2 * q + A[i]) % M2;
        Hstr1 = (Hstr1 * q + B[i]) % M1;
        Hstr2 = (Hstr2 * q + B[i]) % M2;
    }

    int q1n = 1, q2n = 1;
    for(int i = 1; i < n; i++)
    {
        q1n = q1n * q % M1;
        q2n = q2n * q % M2;
    }

    if(Hpat1 == Hstr1 && Hpat2 == Hstr2)
        Sol.push_back(0);

    int Nr = Sol.size();
    for(int i = n; i < m; i++)
    {
        Hstr1 =((Hstr1 - (q1n * B[i-n]) % M1 + M1) * q + B[i]) % M1;
        Hstr2 =((Hstr2 - (q2n * B[i-n]) % M2 + M2) * q + B[i]) % M2;
        if(Hstr1 == Hpat1 && Hstr2 == Hpat2)
        {
            Nr++;
            if(Nr < 1000) Sol.push_back(i-n+1);
        }
    }

    fout << Nr << "\n";
    for(int i = 0; i < Sol.size(); i++)
    {
        fout << Sol[i] << " ";
    }


}