Cod sursa(job #3310908)

Utilizator iccjocIoan CHELARU iccjoc Data 17 septembrie 2025 20:00:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;

int cnt = 0;
vector<int> ans;
int pr[4000005 + 1];
string t, s, k;

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	cin >> t >> s;
	k = t + "#" + s;
	pr[0] = 0;
	for(int i = 1; i < k.size(); i++)
	{
		int j = pr[i - 1];
		while(j > 0 && k[i] != k[j])
		{
			j = pr[j - 1];
		}
		if(k[i] == k[j])
		{
			j++;
		}
		pr[i] = j;
	}
	for(int i = 0; i < k.size(); i++)
	{
		if(pr[i] == t.size())
		{
			ans.push_back(i - 2 * t.size());
		}
	}
	cout << ans.size() << "\n";
	for(int i = 0; i < min((int)(ans.size()), 1000); i++)
	{
		cout << ans[i] << " ";
	}
}