Cod sursa(job #2916181)

Utilizator matwudemagogul matwu Data 28 iulie 2022 12:18:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define EFC cin.tie(nullptr)->ios_base::sync_with_stdio(false)
int d1[5] = { 0, -1, 0, 1, 0 };
int d2[5] = { 0, 0, 1, 0, -1 };
const int mod = 666013;
const int INF = 100000000;
int d11[9] = { 0 , -1, -1, 0, 1, 1, 1, 0, -1 };
int d22[9] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
int est[3] = { 0, -1, 0 };
int est1[3] = { 0, 0, 1 };
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


//----------------------------------

char a[2000002], b[2000002];

int pl[2000002];
vector<int> v;
int main() {

	fin >> a >> b;
	int n = strlen(a);
	int m = strlen(b);

	for (int i = n; i >= 1; i--) a[i] = a[i - 1];
	for (int i = m; i >= 1; i--) b[i] = b[i - 1];


	int k = 0;
	pl[1] = 0;
	for (int i = 2; i <= n; i++) {
		while (k > 0 && a[k + 1] != a[i]) {
			k = pl[k];
		}
		if (a[k + 1] == a[i]) {
			k++;
		}
		pl[i] = k;
	}

	int q = 0;
	for (int i = 1; i <= m; i++) {
		while (q > 0 && a[q + 1] != b[i]) {
			q = pl[q];
		}
		if (a[q + 1] == b[i]) {
			q++;
		}
		if (q == n) {
			v.push_back(i - n );
		}
	}

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