Cod sursa(job #2203997)

Utilizator aurelionutAurel Popa aurelionut Data 13 mai 2018 23:50:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

const int NMAX = 2e6 + 10;
string a, b;
vector <int> v;
int z[NMAX], len;

void Read()
{
	ifstream fin("strmatch.in");
	fin >> a >> b;
	len = a.length();
	fin.close();
}

void Solve()
{
	a = a + "$" + b;
	int left = 0, right = 0;
	for (int k = 1;k < a.length();++k)
	{
		if (k > right)
		{
			left = right = k;
			while (right < a.length() && a[right] == a[right - left])
				++right;
			z[k] = right - left;
			--right;
		}
		else
		{
			int p = k - left;
			if (z[p] < right - k + 1)
				z[k] = z[p];
			else
			{
				left = k;
				while (right < a.length() && a[right] == a[right - left])
					++right;
				z[k] = right - left;
				--right;
			}
		}
	}
}

void Write()
{
	ofstream fout("strmatch.out");
	int cnt = 0, k = 0;
	for (int i = len;i < a.length();++i)
	{
		if (z[i] == len)
		{
			++cnt;
			if (cnt <= 1000)
				v.push_back(i - len -1);
		}
	}
	fout << cnt << "\n";
	for (int i : v)
		fout << i << " ";
	fout.close();
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}