Cod sursa(job #2681669)

Utilizator nouaMocanu Bogdan Gabriel noua Data 6 decembrie 2020 11:34:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;
#define min(a, b) ((a < b) ? a : b)
#define NMax 2000001
char A[NMax], B[NMax];
int pi[NMax];
void MakePi(char* A, int leng) {
	pi[0] = 0;
	int lasti = 0;
	int i = 1;

	while (i < leng) {
		if (A[lasti] == A[i]) {
			pi[i++] = ++lasti;
		}
		else {
			if (lasti != 0)
				lasti = pi[lasti - 1];
			else
				pi[i++] = 0;
		}
	}
}
void reset(int& j) {
	if (pi[j] > 0)
		j = pi[j] - 1;
	else
		j = 0;
}
int main()
{
	int nr = 0;

	vector<int> ind;
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s", A, B);

	MakePi(A, strlen(A));
	if (strlen(A) > strlen(B))
	{
		printf("0\n");
		return 0;
	}
	int j = 0;

	int i = 0;
	while (i < strlen(B)) {
		if (A[j] == B[i]) {
			j++;
			i++;
		}
		if (j == strlen(A)) {
			nr++;
			ind.push_back(i - strlen(A));
			j = pi[j - 1];
		}
		else if (i < strlen(B) && A[j] != B[i]) {
			if (j != 0)
				j = pi[j - 1];
			else
				i++;
		}
	}

	printf("%d\n", nr);
	for (int i = 0; i < min(ind.size(), 1000); i++) {
		printf("%d ", ind[i]);
	}
	return 0;
}