Cod sursa(job #2449536)

Utilizator silviu982001Borsan Silviu silviu982001 Data 20 august 2019 00:12:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

int main()
{
	ifstream fin("strmatch.in");
	string s, p;
	fin >> p;
	fin >> s;
	fin.close();
	
	int *a = new int[p.length()];
	int sol = 0, j = 0;
	vector<int> v;
	a[0] = 0;
	for (int i = 1; i < p.length();)
		if (p[j] == p[i])
		{
			a[i] = j + 1;
			++i;
			++j;
		}
		else if (j != 0)
			j = a[j - 1];
		else
		{
			a[i] = 0;
			++i;
		}

	j = 0;
	for (int i = 0; i < s.length();)
	{
		if (s[i] == p[j])
		{
			++i;
			++j;
		}
		else if (j != 0)
		{
			j = a[j - 1];
		}
		else
		{
			++i;
		}

		if (j == p.length())
		{
			++sol;
			if (v.size() < 1000)
				v.push_back(i - p.length());
			//j = a[j - 1];
		}
	}
	ofstream fout("strmatch.out");
	fout << sol << '\n';
	for (int i = 0; i < v.size(); ++i)
		fout << v[i] << ' ';
	fout.close();

	return 0;
}