Cod sursa(job #2800689)

Utilizator sanzianagrecuSanziana Grecu sanzianagrecu Data 13 noiembrie 2021 18:20:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> KMP(string s){

	s = "$" + s;

	vector <int> pi(s.size());

	int k = 0;

	for (int i = 2; i < (int) s.size(); ++ i){
		while (k && s[i] != s[k + 1])
			k = pi[k];
		if (s[i] == s[k + 1])
			k ++;
		pi[i] = k;
	}

	pi.erase(pi.begin());

	return pi;
}

vector <int> GasestePotriviri(string s, string t){

	vector <int> kmp = KMP(s + '$' + t);
	vector <int> sol; 

	for (int i = (int) s.size() + 1; i < (int) kmp.size(); ++ i)
		if (kmp[i] == (int) s.size())
			sol.push_back(i - (2 * (int) s.size()));


/*
*  S = "abab"
*  T = "ababcababab"
*  S + '$' + T = abab$ababcababab
*/

	return sol;
}




int main(){


	string s, t;
	fin >> s >> t;
	
	vector <int> sol = GasestePotriviri(s, t);

	int n = (int) sol.size();

	fout << n << '\n';

	if(n > 1000)
		n = 1000;
	for (int i = 0; i < n; ++ i)
		fout << sol[i] << ' ';


	return 0;
}