Cod sursa(job #2985080)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 25 februarie 2023 17:13:09
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000000;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int BASE = 257;

int n, m;
string A, B;
int z[2 * NMAX + 1];
int nr, v[1001];

int main() {
	fin >> A >> B;
	n = A.size();
	m = B.size();

	if(n > m) {
		fout << "0\n";
		return 0;
	}

	A = A + "#" + B;

	z[0] = 0;
	for(int i = 1; i < (int) A.size(); i++) {
		while(i + z[i] < (int) A.size() && A[z[i]] == A[i + z[i]]) {
			z[i]++;
		}
	}

	for(int i = n + 1; i < (int) A.size(); i++) {
		if(z[i] == n) {
			nr++;
			if(nr <= 1000) {
				v[nr] = i - n - 1;
			}
		}
	}

	fout << nr << '\n';
	for(int i = 1; i <= min(1000, nr); i++) {
		fout << v[i] << " ";
	}
	return 0;
}