Cod sursa(job #2800684)

Utilizator sanzianagrecuSanziana Grecu sanzianagrecu Data 13 noiembrie 2021 17:54:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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);

	fout << sol.size() << '\n';
	for (auto i : sol)
		fout << i << ' ';


	return 0;
}