Cod sursa(job #2681656)

Utilizator nouaMocanu Bogdan Gabriel noua Data 6 decembrie 2020 11:12:42
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 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;
		}
	}
}
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 lasti = 0;
	for (int i = 0; i < strlen(B); i++) {
		if (A[j] == B[i]) {
			j++;
		}
		else if(j!=0){
			if (pi[j] > 0)
				j = pi[j] - 1;
			else
				j = 0;
		}
		if (j == strlen(A)) {
			nr++;
			ind.push_back((i + 1) - strlen(A));
			j = 0;
			if (A[j] == B[i]) {
				j++;
			}
		}
	}
	printf("%d\n", nr);
	for (int i = 0; i < min(ind.size(), 1000); i++) {
		printf("%d ", ind[i]);
	}
	return 0;
}