Cod sursa(job #2462020)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 26 septembrie 2019 17:53:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int MAXN = 4*1e6 + 5;

char t1[MAXN],t2[MAXN],t[MAXN];
int Z[MAXN];

int main() {
		
	fin >> (t1 + 1) >> (t2 + 1);
	int n = strlen(t1 + 1), m =strlen(t2 + 1),cnt = 0;
	for ( int i = 1; i <= n; ++i)
		t[++cnt] = t1[i];
	t[++cnt] = '$';
	for ( int i = 1; i <= m; ++i)
		t[++cnt] = t2[i];
	int index = 1,l = 0,r = 0,q;
	Z[1] = 1;
	q = strlen(t+1);
	for ( int i = 2; i <= q; ++i) 
		if (i >= r) {
			r = l = i;
			while(t[r] == t[r-l + 1] and r <= q)
					++r;
			--r;
			Z[i] = r-l+1;
		}
		else {
			int lung = r - i;
			int poz = i - l;
			if ( Z[poz] <= lung)
				Z[i] = Z[poz];
			else {
				while ( t[r] == t[r-l+1] and r <= q)
					++r;
				--r;
				Z[i] = r-l+1;
				l = i;
			}
		}
	 cnt = 0;
		for ( int i = n+1; i <= q; ++i)
			if ( Z[i] == n)
				++cnt;
		
	fout << cnt << "\n";
	for ( int i = n+1; i <= q; ++i)
			if ( Z[i] == n)
				fout << i - n-2 << " ";
				
}