Cod sursa(job #1072292)

Utilizator VincentVegaVincent Vega VincentVega Data 4 ianuarie 2014 12:15:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

char A[2000005], B[2000005];
int N, M;
int S, V[1005];
int pr[2000005];

int main()
{
	fin >> (A + 1) >> (B + 1);
	N = strlen(A + 1); M = strlen(B + 1);
	
	for (int i = 2, q = 0; i <= N; ++i)
	{
		while (q && A[i] != A[q + 1])
			q = pr[q];
		if (A[i] == A[q + 1])
			++q;
		pr[i] = q;
	}
	
	for (int i = 1, q = 0; i <= M; ++i)
	{
		while (q && B[i] != A[q + 1])
			q = pr[q];
		if (B[i] == A[q + 1])
			++q;
		if (q == N)
		{
			++S;
			if (V[0] < 1000)
				V[++V[0]] = i - N;
		}
	}
	
	fout << S << '\n';
	for (int i = 1, aux = min(V[0], 1000); i <= aux; ++i)
		fout << V[i] << ' ';
	fin.close();
	fout.close();
}