Cod sursa(job #2655758)

Utilizator PaulTPaul Tirlisan PaulT Data 5 octombrie 2020 14:43:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

using VI = vector<int>;

const int MaxN = 2000010;
int n, m;
VI pi, res;
char prop[MaxN], word[MaxN];

void Read();
void KMP();
void Write();

int main()
{
	Read();
	KMP();
	Write();
}

void KMP()
{
	pi = VI(n);
	int q{0};
	for (int i = 1; i < n; i++)
	{
		while (q > 0 && word[q] != word[i])
			q = pi[q - 1];
		if (word[q] == word[i])
			q++;
		pi[i] = q;
	}
	
	q = 0;
	for (int i = 0; i < m; i++)
	{
		while (q > 0 && (q == n || word[q] != prop[i]))
			q = pi[q - 1];
		if (word[q] == prop[i])
			q++;
		if (q == n)
			res.emplace_back(i - n + 1);
	}
}

void Write()
{
	ofstream fout("strmatch.out");
	fout << res.size() << '\n';
	for (const int& pos : res)
		fout << pos << ' ';
}

void Read()
{
	ifstream fin("strmatch.in");
	fin.getline(word, MaxN + 1);
	fin.getline(prop, MaxN + 1);
	n = strlen(word);
	m = strlen(prop);
}