Cod sursa(job #2692580)

Utilizator Iustin01Isciuc Iustin - Constantin Iustin01 Data 3 ianuarie 2021 11:37:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb

#include <bits/stdc++.h>
#define NMax 2000001
using namespace std;

int m,n;
char a[NMax], b[NMax];
int pi[NMax], pos[1024];
int ct;

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

void Peg();
void Read();
void Rez();
void Afis();

int main()
{
    Read();
    Peg();
    Rez();
    Afis();
    return 0;
}

void Read()
{
    fin.getline(a,NMax);
    fin.getline(b,NMax);
    m=strlen(a);
    n=strlen(b);
    for(int i=n;i;i--) b[i]=b[i-1];
    for(int i=m;i;i--) a[i]=a[i-1];
    b[0]=a[0]=' ';
}

void Peg()
{
    pi[1]=0;
    int q=0;
	for(int i=2;i<=m;i++)
	{
		while(q && a[q+1]!=a[i]) q=pi[q];
		if(a[q+1]==a[i]) q++;
		pi[i]=q;
	}
}

void Rez()
{
    int q=0;
    for(int i=1;i<=n;i++)
	{
		while(q && a[q+1]!=b[i]) q=pi[q];
		if(a[q+1]==b[i]) q++;
		if(q==m)
		{
			q=pi[m];
			ct++;
			if(ct<=1000)
				pos[ct]=i-m;
		}
	}
}

void Afis()
{
    fout<<ct<<'\n';
    for(int i=1;i<=min(ct,1000);i++)
        fout<<pos[i]<<' ';
}