Cod sursa(job #2063144)

Utilizator Tyler_BMNIon Robert Gabriel Tyler_BMN Data 11 noiembrie 2017 09:48:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>;
#include <string>;
#include <vector>;

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

string text, substring;
vector<int> pattern,rez;

void makePattern()
{
	for (int i = 1, j = 0; i < substring.length(); i++)
	{
		while (substring[i] != substring[j] && j > 0)
			j = pattern[j - 1];
		if (substring[i] == substring[j])
			pattern[i] = ++j;
	}
}

void searchPattern()
{
	for (int i = 0, j = 0; i < text.length(); i++)
	{
		while (text[i] != substring[j] && j > 0)
			j = pattern[j - 1];
		if (text[i] == substring[j])
		{
			if (j == substring.length() - 1)
			{
				rez.push_back(i - substring.length() + 1);
				j = pattern[j];
			}
			else
				j++;
		}
	}
}


int main() {
	fin >> substring >> text;
	pattern.reserve(substring.length());
	makePattern();
	searchPattern();
	fout << rez.size() << "\n";
	for (int i = 0; i < 1000 && i < rez.size(); i++) {
		fout << rez[i]<<" ";
	}
}