Cod sursa(job #3212575)

Utilizator Costi2mFulina Costin Costi2m Data 11 martie 2024 21:54:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int M, N, cont=0;
char A[2000000], B[2000000];
queue<int> coada;

void search()
{
    int i, j;
    int h = 1;
    int txt = 0;
    int model = 0;
    
    int d = 256; int p = 101;
    
    h = pow(d, M-1);
    h = h%p;
    
    for(i=0; i<M; i++)
    {
        model = (model * d + A[i]) % p;
        txt = (txt * d +  B[i]) % p;
    }
    
    for(i=0; i <= N-M; i++)
    {
        if(model == txt)
        {
            for(j = 0; j<M; j++)
                if(B[i+j] != A[j]) 
                    break;
            
            if(j==M)
            {
                cont++;
                coada.push(i);
            }
        }
        
        if(i < N-M)
        {
            txt = ( d * (txt - B[i] * h) + B[i+M] ) % p;
            if(txt < 0) txt += p;
        }
    }
}

int main()
{
    fin >> A >> B;
    M = strlen(A);
    N = strlen(B);
    
    search();
    
    fout << cont << "\n";
    while(!coada.empty())
    {
        fout << coada.front() << " ";
        coada.pop();
    }
    return 0;
}