Cod sursa(job #2482575)

Utilizator invoIlioi Alexandru invo Data 28 octombrie 2019 16:17:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
#include<iostream>
#include<string.h>
#define MAX 2000005
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int m, n, k, c, pi[MAX];
char N[MAX], M[MAX];	//N - pattern, M - big string
int a[MAX];
//ABA
//CABBCABABAB
//0001123
//k = 0
void prefixCalculation()
{
	int j = 0;
	for (int i = 1; i < n; ++i)
	{
		while (j > 0 && N[i] != N[j])
			j = pi[j - 1];
		if (N[i] == N[j])
			j++;
		pi[i] = j;
	}
}

//AAAAA
//ABA
//010

void KMP()
{
	int q = 0;
	for (int i = 0; i < m; ++i)
	{
		while (q > 0 && N[q] != M[i])
			q = pi[q - 1];
		if (N[q] == M[i])
			++q;
		if (q == n)
		{
			a[c++] = i - n + 1;
			if (c > 1000)
				return;
		}
	}
}

void readData()
{
	f.getline(N, MAX);
	f.getline(M, MAX);
	n = strlen(N);
	m = strlen(M);
}

int main()
{
	readData();
	prefixCalculation();
	KMP();
	g << c << '\n';
	for (int i = 0; i < c; ++i)
	{
		g << a[i] << ' ';
	}
}