Cod sursa(job #1781502)

Utilizator MickeyTurcu Gabriel Mickey Data 16 octombrie 2016 22:17:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<math.h>
#include<unordered_set>
#include<set>
#include<iomanip>
#include<bitset>
using namespace std;
int M, N;
char A[2002002], B[2002002];
int pi[2002002], pos[1010];
void make_prefix(void)
{
	int i, q = 0;
	for (i = 2, pi[1] = 0; i <= M; ++i)
	{
		while (q && A[q + 1] != A[i])
			q = pi[q];
		if (A[q + 1] == A[i])
			++q;
		pi[i] = q;
	}
}
int i, q = 0, n = 0;
int main(void)
{
	
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f >> (A+1);
	M = strlen(A+1);
	f >> (B+1);
	N = strlen(B+1);
	make_prefix();
	for (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];
			++n;
			if (n <= 1000)
				pos[n] = i - M;
		}
	}

	g << n << '\n';
	for (i = 1; i <= min(n, 1000); i++)
		g << pos[i]<<' ';
	g << '\n';

	return 0;
}