Cod sursa(job #2350388)

Utilizator SmokeCiocotisan Cosmin Smoke Data 21 februarie 2019 12:00:39
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb


#include "pch.h"
#include <iostream>
#include <fstream>
#include< cstring>

#define minim(a, b) ((a < b) ? a : b)
#define max 200


using namespace std;

char s1[max], s2[max];
int pi[max ];
int n, m;


void citire()
{
	ifstream in("strmatch.in");


		in.getline(s1, max);
		in.getline(s2, max);
		
	
	
	n = strlen(s1);
	m = strlen(s2);

	for (int i = n; i > 0; i--)
		s1[i] = s1[i - 1];
	for (int j = m; j > 0; j--)
		s2[j] = s2[j - 1];


}

void make_prefix()
{
	int q = 0;
	int i;
	//cout << s1 << endl;

	for (i = 2, pi[1] = 0; i <= n; i++)
	{
		while (q && s1[q + 1] != s1[i])
			q = pi[q];
		if (s1[q + 1] == s1[i])
			q++;
	
		pi[i] = q;

	}


}

int main()
{
	citire();
	
	//cout << s2 << endl;

	make_prefix();
	int contor = 0;
	int pozitions[max];

	int q = 0;
	for (int i = 1; i <= m; i++)
	{
		while (q && s1[q + 1] != s2[i])
			q = pi[q];
		if (s1[q + 1] == s2[i])
			q++;

		if (q == n)
		{
			
			 if(contor<=1000)
			pozitions[++contor] = i - n;
			



		}



	}

	ofstream out("strmatch.out");
	out << contor<< endl;

	for (int i = 1; i <= contor; i++)
		out << pozitions[i] << " ";
	



	

	return 0;
}