Cod sursa(job #1231846)

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

#define LMAX 2000009

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

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

void Urmatorul(char *P)
{
	int k = -1;
	urm[0] = 0;
	for (int i = 1; i < strlen(P); ++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 = strlen(T);
	m = strlen(P);

	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)