Cod sursa(job #2681676)

Utilizator nouaMocanu Bogdan Gabriel noua Data 6 decembrie 2020 11:47:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 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, int pi[]) {
	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;
		}
	}
}

int main()
{
	int nr = 0;

	vector<int> ind;
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s", A, B);
	int M = strlen(A);
	int N = strlen(B);
	MakePi(A, M, pi);
	if (M > N)
	{
		{
			printf("0\n");
			return 0;
		}
	}
	int j = 0;

	int i = 0;
	while (i < N) {
		if (A[j] == B[i]) {
			j++;
			i++;
		}
		if (j == M) {
			nr++;
			ind.push_back(i - M);
			j = pi[j - 1];
		}
		else if (i < N && 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;
}