Cod sursa(job #2744975)

Utilizator dream3rDavid Pop dream3r Data 25 aprilie 2021 17:11:54
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");

int main()
{
	string pattern;
	string s;
	int printedIndex = 0;
	vector<int>ans;
	f >> pattern;
	f >> s;
	vector<int>lsp(pattern.size(), 0);
	int j = 0;
	for (int i = 1; i < pattern.size(); i++)
	{
		if (pattern[i] == pattern[j])
		{
			lsp[i] = ++j;
		}
		else if (j != 0)
		{
			j = lsp[i - 1];
		}
	}
	j = 0;

	for (size_t i = 0; i < s.size(); i++)
	{
		if (s[i] == pattern[j])
		{
			j++;
			if (j == pattern.length())
			{
				printedIndex++;
				ans.push_back(i - j + 1);
				j = lsp[j - 1];
			}
		}
		else
		{
			if (j != 0)
			{
				j = lsp[j - 1];
				i--;
			}
		}
	}
	o << printedIndex << "\n";
	printedIndex = min(1000, printedIndex);
	for (size_t i = 0; i < printedIndex; i++)
	{
		o << ans[i] << " ";
	}
}