Cod sursa(job #2909893)

Utilizator vladiiiVlad Martiniuc vladiii Data 16 iunie 2022 17:14:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int pos[1000], pin;

int main() {
	
	f >> a >> b;
	vector<int> ta(a.size(), -1);
	for (size_t i = 1; i < ta.size(); i++)
	{
		if (a[i] == a[ta[i - 1] + 1]) ta[i] = ta[i - 1] + 1;
		else if (a[i] == a[0]) ta[i] = 0;
	}

	int j = -1;
	for (size_t i = 0; i < b.size(); i++)
	{
		if (b[i] == a[j+1]) {
			j++;
			if (j == a.size() - 1) { 
				if (pin < 1000) pos[pin] = i - j;
			pin++; j = ta[j]; }
		}
		else if(j != -1) {
			j = ta[j]; i--;
		}
	}

	g << pin << endl;
	for (size_t e = 0; e < pin && e < 1000; e++)
	{
		g << pos[e] << " ";
	}
}