Cod sursa(job #2481815)

Utilizator invoIlioi Alexandru invo Data 27 octombrie 2019 14:21:53
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include<iostream>
#define MAX 2000001
using namespace std;

FILE* f;
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()
{
	pi[0] = 0;
	for (int i = 1; i < n; ++i)
	{
		k = pi[i - 1];
		while (k > 0 && N[k] != N[i])
			k = pi[k - 1];
		if (N[i] == N[k])
			k++;
		pi[i] = k;
	}
}

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

void readData()
{
	char c = 0;
	f = fopen("strmatch.in", "r");
	n = 0;
	m = 0;
	while (c != '\n')
	{
		c = getc(f);
		if (c == ' ' || c == '\n')
			continue;
		N[n] = c;
		n++;
	}
	c = 1;
	while (c != EOF)
	{
		c = getc(f);
		if (c == ' ' || c == '\n')
			continue;
		M[m] = c;
		m++;
	}
}

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