Cod sursa(job #3295215)

Utilizator tomaionutIDorando tomaionut Data 3 mai 2025 17:02:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

char s1[2000005], s2[2000005];
int lsp[2000005], sol[1005], cnt;

void KMP(char s1[], char s2[])
{
	int i, j, n, m;
	n = strlen(s1);
	m = strlen(s2);
	
	//construim lsp-ul
	i = 1;
	j = 0;
	while (i < n)
	{
		if (s1[i] == s1[j])
		{
			lsp[i] = j + 1;
			i++;
			j++;
		}
		else
		{
			if (j)
				j = lsp[j - 1];
			else
				i++;
		}
	}

	//cautam patternurile
	i = j = 0;
	while (i < m)
	{
		if (s1[j] == s2[i])
		{
			i++;
			j++;
		}
		else
		{
			if (j)
				j = lsp[j - 1];
			else
				i++;
		}

		if (j == n)
		{
			if (cnt <= 1000)
			sol[++cnt] = i - n;
			j = lsp[j - 1];
		}
	}

	fout << cnt << "\n";
	for (i = 1; i <= min(1000, cnt); i++)
		fout << sol[i] << " ";
}

int main()
{
	fin >> s1 >> s2;
	KMP(s1, s2);

	return 0;
}