Cod sursa(job #1231840)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 21 septembrie 2014 17:17:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;

#define LMAX 2000009

#pragma warning(push)
#pragma warning(disable:4996)

string T, P;
int urm[LMAX];
int n, m;
int counter = 0;
vector<int> solutii;

void Urmatorul(string P)
{
	int k = -1;
	urm[0] = 0;
	for (int i = 1; i < P.size(); ++i)
	{
		while (k > 0 && P[k + 1] != P[i])
			k = urm[k];
		if (P[k + 1] == P[i])
			k++;
		urm[i] = k;
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	cin >> P;
	cin >> T;

	Urmatorul(P);

	n = T.size();
	m = P.size();

	int k = -1;

	for (int i = 0; i < n; ++i)
	{
		while (k > 0 && P[k + 1] != T[i])
			k = urm[k];
		if (P[k + 1] == T[i])	// s-au potrivit
			k++;
		if (k == m - 1)
		{
			solutii.push_back(i - m + 1);
			k = urm[k];
			counter++;

		}
	}

	printf("%d\n", counter);

	for (int i = 0; i < solutii.size(); ++i)
	{
		printf("%d ", solutii[i]);
	}

	return 0;
}

#pragma warning(pop)