Cod sursa(job #2962987)

Utilizator Vali_nnnValentin Nimigean Vali_nnn Data 9 ianuarie 2023 22:22:17
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include<cstring>
#define minim(a, b) ((a < b) ? a : b)
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int m, n,nr;
char a[20005], b[20005];
int p[20005], pos[1024];

void prefix()
{
	int i, q = 0;

	for (i=2,p[1]=0;i<=m;++i)
	{
		while (q && a[q+1] != a[i])
			q=p[q];
		if (a[q+1] == a[i])
			++q;
		p[i] = q;
	}
}

int main()
{
	int i, q = 0, n = 0;



f>>a;
f>>b;

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



	for (i=m;i>=1;i--)
        a[i]=a[i-1];
    a[0] =' ';
	for (i=n;i>=1;i--)
    b[i]=b[i-1];
    b[0] =' ';

prefix();



	for (i=1;i<=n;i++)
	{
		while (q && a[q+1]!=b[i])
			q=p[q];
		if (a[q+1]==b[i])
			q++;
		if (q==m)
		{
			q=p[m];
			nr++;
			if(n<=1000)
				pos[nr]=i-m;
		}
	}

	g<<nr<<'\n';

	if(nr>1000)
	for (i=1;i<=1000;i++)
    g<<pos[i]<<" ";
    else
	for (i=1;i<=nr;i++)
    g<<pos[i]<<" ";

	return 0;
}