Mai intai trebuie sa te autentifici.

Cod sursa(job #2933116)

Utilizator lolismekAlex Jerpelea lolismek Data 4 noiembrie 2022 17:46:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

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

//ifstream fin("euclid3.in");
//ofstream fout("euclid3.out");

const int NMAX = 4e6;
int kmp[NMAX + 1];

string s;

void Kmp(){
	kmp[1] = 0;
	for(int i = 2; i <= (int)s.size() - 1; i++){
		int l = kmp[i - 1];
		while(l != 0 && s[l + 1] != s[i])
			l = kmp[l];
		if(s[l + 1] == s[i])
			kmp[i] = l + 1;
	}
}

int main(){

	string s1, s2;
	fin >> s1 >> s2;

	s = "$" + s1 + "%" + s2;

	Kmp();

	int ans = 0;
	for(int i = (int)s1.size() + 2; i <= (int)s.size() - 1; i++)
		ans += (kmp[i] == (int)s1.size());

	fout << ans << '\n';

	int ind = 0;
	for(int i = (int)s1.size() + 2; i <= (int)s.size() - 1; i++)
		if(kmp[i] == (int)s1.size() && ind < 1000){
			fout << i - 2 * (int)s1.size() << ' ', ++ind;

			if(ind == 1000)
				return 0;
		}

	return 0;
}