Cod sursa(job #2802710)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 18 noiembrie 2021 18:04:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<bits/stdc++.h>
using namespace std;

const int p=67;
const int mod = 1000000007;
vector<int> solutie;
char a[2000005],b[2000005];
long long H,H0,pw;

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

    fin>>a;

    fin>>b;

    H = 0;

    int n=strlen(a);
    int m=strlen(b);

    for(int i=0;i<n;i++)
        H = (H * p + a[i])%mod;



    H0 =0;

    for(int i=0;i<n;i++)
        H0 = (H0 * p + b[i])%mod;


    if(H == H0)
    {
        solutie.push_back(0);
    }

    pw = 1;

    for(int i=1;i<n;i++)
        pw = (pw * p) %mod;

    //pw este p^(n-1)

    for (int i=1;i<m;i++)
    {
        if((i+n-1)<m)
        {
            //b[i-1]
            //Secventa noastra curenta incepe la b[i]. Cea de dinainte avea b[i-1]

            //Trebuie sa scadem b[i-1] * p^(n-1)

            H0  = (H0 - ( (pw*b[i-1])%mod ) + mod) %mod;

            H0 = (H0 * p + b[i+n-1]) %mod;

            if(H == H0)
            {
                solutie.push_back(i);
            }
        }

    }

    int sz = solutie.size();

    fout<<solutie.size()<<'\n';

    for(int i=0;i<min(1000,sz);i++)
        fout<<solutie[i]<<' ';

    return 0;
}