Cod sursa(job #2714332)

Utilizator 0021592Grecu rares 0021592 Data 1 martie 2021 18:13:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int c[2000004], l, v[2000004], cnt=0;
int main()
{
	fin >> a >> b;
	for (int i = 1; i < a.size(); i++)
	{
		while (a[l] != a[i] && l != 0)
		{
			l = c[l - 1];
		}
		if (a[l] == a[i])
		{
			l++;
		}
		c[i] = l;
	}
	l = 0;
	for (int i=0; i<b.size(); i++)
	{
		while (a[l] != b[i] && l != 0)
		{
			l = c[l - 1];
		}
		if (a[l] == b[i])
		{
			l++;
		}
		if (l == a.size())
		{
			cnt++;
			v[cnt] = i - a.size() + 1;
			l = c[l-1];
		}
	}
	fout << cnt << endl;
	if (cnt > 1000) cnt = 1000;
	for (int i = 1; i <= cnt; i++)
	{
		fout << v[i] << " ";
	}
}