Cod sursa(job #2456540)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 14 septembrie 2019 16:33:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define NMAX 2000003
int ans, ind, lps [NMAX];
string A, B;
vector <int> v;
int main (){
	fin >> A >> B;
	for (int i = 1; i < A.size ();){
		if (A [ind] == A [i]){
			lps [i ++] = ++ ind;
		}
		else if (ind != 0)
			ind = lps [ind - 1];
		else lps [i ++] = 0;
	}
	ind = 0;
	for (int i = 0; i < B.size ();){
		if (B [i] == A [ind])
			i ++, ind ++;
		else if (ind != 0)
			ind = lps [ind - 1];
		else i ++;
		if (ind == A.size ()){
			ans ++;
			if (v.size() < 1000)
				v.push_back (i - A.size());
		}
	}
	fout << ans << '\n';
	for (int i = 0; i < v.size(); ++i)
		fout << v [i] << " ";
	return 0;
}