Cod sursa(job #2226007)

Utilizator lorena1999Marginean Lorena lorena1999 Data 29 iulie 2018 10:39:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define MAX 4000000

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[MAX], b[MAX];

int hashTableA[MAX], hashTableB[MAX];

queue < int > q;

bool isIndeed(int idx, int l)
{
    int hA=0, i=idx+l-1;
    while(idx<=i)
    {
        int sum = hashTableB[i]-hashTableB[idx-1];
        int sum2 = hashTableA[l]-hashTableA[hA];
        hA++;
        idx++;
        if(sum!=sum2)
            return false;
    }
    return true;
}

int main()
{
    f>>(a+1)>>(b+1);
    int la=strlen(a+1);
    int lb=strlen(b+1);
    for(int i=1; i<=la; i++)
    {
        hashTableA[i]=hashTableA[i-1]+int(a[i]);
        //cout<<hashTableA[i]<<" ";
    }
    //cout<<'\n';
    for(int i=1; i<=lb; i++)
    {
        hashTableB[i]=hashTableB[i-1]+int(b[i]);
        //cout<<hashTableB[i]<<" ";
    }
    //cout<<'\n';
    for(int i=1; i<=lb-la+1; i++)
    {
        int sum = hashTableB[i+la-1]-hashTableB[i-1];
        if(sum==hashTableA[la])
        {
            //cout<<"YES "<<i<<endl;
            if(isIndeed(i, la))
                q.push(i);
        }
    }
    g<<q.size()<<'\n';
    while(!q.empty())
    {
        int x = q.front();
        g<<x-1<<" ";
        q.pop();
    }
}