Cod sursa(job #2404124)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 12 aprilie 2019 12:29:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");


const int Dim = 2 * 1e6 + 5;
char A[Dim],B[Dim],C[Dim];
int Z[Dim];
vector < int > V;

int main() {

	
	fin >> (A + 1) >> (B + 1);
	int n = strlen(A + 1), m = strlen(B + 1);
	int idk = 0;
	for ( int i = 1; i <= n; ++i)
		C[++idk] = A[i];
	C[++idk] = '$';
	int ss = idk;
	for ( int i = 1; i <= m; ++i)
		C[++idk] = B[i];
	n = idk;
	Z[1] = n;
	int l = 0, r = 0;
	for  (int i = 2	; i <= n; ++i) {
		if ( r >= i) Z[i] = min(r-i+1,Z[i-l+1]);
		while ( C[i+Z[i]] == C[Z[i]+1]) Z[i]++;
		if ( r < i + Z[i] - 1) r = i+Z[i]-1, l = i;  	
	} 
	for ( int i = ss + 1; i <= n; ++i)
		if( Z[i] >= ss - 1)
			V.push_back(i -ss);
	fout << V.size() << "\n";
	for  ( const auto i : V)
		fout << i-1 << " ";

}