Cod sursa(job #1954200)

Utilizator vladttturcuman vlad vladtt Data 5 aprilie 2017 11:40:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <cstring>
#include <vector>

#define P 80
#define Mod1 100007
#define Mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000010];
char b[2000010];

int main()
{
    vector<int> v;

    fin>>a;
    fin>>b;

    int NA = strlen(a);
    int NB = strlen(b);

    if(NA > NB)
    {
        fout<<0<<'\n';
        return 0;
    }

    int HashA1 = 0;
    int HashA2 = 0;

    int Pow1 = 1;
    int Pow2 = 1;

    for(int i=0;i<NA;i++)
    {
        HashA1 = (HashA1 * P + a[i]- '0') % Mod1;
        HashA2 = (HashA2 * P + a[i]- '0') % Mod2;

        if(i!=0)
        {
            Pow1 = Pow1 * P % Mod1;
            Pow2 = Pow2 * P % Mod2;
        }
    }


    int HashB1 = 0;
    int HashB2 = 0;

    for(int i=0;i<NA;i++)
    {
        HashB1 = (HashB1 * P + b[i]- '0') % Mod1;
        HashB2 = (HashB2 * P + b[i]- '0') % Mod2;
    }

    int S = 0;
    if(HashA1 == HashB1 && HashA2 == HashB2)
    {
        v.push_back(0);
        S++;
    }


    for(int i=NA;i<NB;i++)
    {
        HashB1 = (((HashB1 - Pow1 * (b[i-NA] - '0')) % Mod1 + Mod1) * P + b[i] - '0') % Mod1;
        HashB2 = (((HashB2 - Pow2 * (b[i-NA] - '0')) % Mod2 + Mod2) * P + b[i] - '0') % Mod2;

        if(HashA1 == HashB1 && HashA2 == HashB2 && S++ < 1000)
            v.push_back(i-NA+1);
    }

    fout<<S<<'\n';

    for(int i=0;i<v.size();i++)
        fout<<v[i]<<' ';


    return 0;
}