Cod sursa(job #2680775)

Utilizator nouaMocanu Bogdan Gabriel noua Data 4 decembrie 2020 12:51:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>

using namespace std;
#define min(a, b) ((a < b) ? a : b)
char A[2000005], B[2000005];
int pi[2000005];
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));
	int j = 0;
	int lasti = 0;
	for (int i = 0; i < strlen(B); i++) {
		lasti = i;

		while (A[j] == B[i]) {
			j++;
			i++;
			if (j == strlen(A) - 1 && A[j] == B[i]) {
				nr++;
				ind.push_back(lasti);
				j = 0;
				lasti = i;
			}
		}
		if (j != 0)
			j = pi[j] - 1;
	}
	printf("%d\n", nr);
	for (int i = 0; i < min(ind.size(), 1000); i++) {
		printf("%d ", ind[i]);
	}
}