Cod sursa(job #2223154)

Utilizator PescaruVictorPescaru Victor PescaruVictor Data 19 iulie 2018 10:15:21
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
//#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int lgA, lgB, ap;
char a[2000010], b[2000010];
int v[1005];
queue<int> q[2];

int main()
{
    int act=0, poz;
    cin>>a>>b;
    lgA=strlen(a);
    lgB=strlen(b);

    for(int i=0; i<lgB; ++i)
    {
        if(i+lgA-1 < lgB && b[i] == a[0])
            q[1^act].push(1);
        while(!q[act].empty())
        {
            poz = q[act].front();
            q[act].pop();
            if(poz == lgA)
            {
                ++ap;
                if(ap <= 1000)
                    v[ap] = i-lgA;
            }
            else if(b[i] == a[poz])
                q[1^act].push(poz+1);
        }
        act = 1^act;
    }
    cout<<ap<<'\n';
    for(int i=1; i<=min(ap, 1000); ++i)
        cout<<v[i]<<' ';
    return 0;
}