Cod sursa(job #2480835)

Utilizator ianiIani Biro iani Data 26 octombrie 2019 10:34:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 2000005

using namespace std;

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

char a[NMAX],b[NMAX];
int n,m,l[NMAX],out[1005];

void prefix()
{
    int j=0;
    for (int i=2;i<=n;i++)
	{
		while(j!=0&&a[i]!=a[j+1])
			j=l[j];
		if (a[i]==a[j+1])
			j++;
		l[i]=j;
	}
}

int main()
{
    fin.getline(a+1,NMAX);
	fin.getline(b+1,NMAX);
	n=strlen(a+1);
	m=strlen(b+1);
	prefix();
	int j=0,nr=0;
    for (int i=1;i<=m;i++)
	{
		while(j!=0&&b[i]!=a[j+1])
			j=l[j];
		if (b[i]==a[j+1])
			{
				j++;
				if (j==n)
					{
						if (nr<=1000)
						out[nr]=i-n;
						nr++;
					}
			}
	}
	fout<<nr<<'\n';
	for (int i=0;i<nr&&i<1000;i++)
		fout<<out[i]<<' ';
    return 0;
}