Cod sursa(job #2916176)

Utilizator matwudemagogul matwu Data 28 iulie 2022 12:05:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 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");
	
 
	
 
	
//----------------------------------
	
 
	
string a, b;
	
vector<int> v;
	
int pi[2000001];
	
int main() {
	
 
	
	fin >> a >> b;
	
	int n = a.length(), m = b.length();
	
	int k = 0;
	
	pi[1] = 0;
	
	for (int i = 2; i <= m; i++) {
	
		while (k > 0 && a[k] != a[i - 1]) {
	
			k = pi[k];
	
		}
	
		if (a[k] == a[i - 1]) {
	
			k++;
	
		}
	
		pi[i] = k;
	
	}
	
	int q = 0;
	
	for (int i = 1; i <= m; i++) {
	
		while (q > 0 && a[q] != b[i - 1]) {
	
			q = pi[q];
	
		}
	
		if (a[q] == b[i - 1]) {
	
			q++;
	
		}
	
		if (q == n) {
	
			v.push_back(i - n);
	
		}
	
	}
	
 
	
	fout << v.size() << '\n';
	
	for (auto i : v) {
	
		fout << i << " ";
	
	}
	
}