Cod sursa(job #2717261)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 6 martie 2021 21:20:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[2000001], B[2000001];
int pi[2000001], pos[1001];

int main(){

	f >> (A + 1) >> (B + 1);

	int N = strlen(A + 1), M = strlen(B + 1), q = 0, n = 0;

	for(int i = 2;i <= N;i++){
		while(q && A[q + 1] != A[i])
			q = pi[q];
		if(A[q + 1] == A[i])
			q++;
		pi[i] = q;
	}

	q = 0;
	for(int i = 1;i <= M;i++){
		while(q && A[q + 1] != B[i])
			q = pi[q];
		if(A[q + 1] == B[i])
			q++;

		if(q == N){
			q = pi[N], n++;
			if(n <= 1000)
				pos[n] = i - N;
		}
	}

	g << n << "\n";
	for(int i = 1;i <= min(n, 1000);i++)
		g << pos[i] << " ";

}