Cod sursa(job #1289967)

Utilizator tudi98Cozma Tudor tudi98 Data 10 decembrie 2014 17:32:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
using namespace std;
#define q 73
#define M1 666013
#define M2 100007

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);

    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)
        {
            Sol.push_back(i-n+1);
            if(Sol.size() == 1000) break;
        }
    }

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


}