Cod sursa(job #2000583)

Utilizator epermesterNagy Edward epermester Data 14 iulie 2017 10:40:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <string>
#include <vector>
#include <iterator>
using namespace std;

int n, m, s=0;

void pattern(string &A, int* p, int i, int j) {
	while (i < n) {
		if (A[i] == A[j]) {
			p[i] = j + 1;
			i++;j++;
		}
		else if (j == 0) {
			p[i] = p[j];
			i++;
		}
		else j = p[j - 1];
	}
}

void compare(string &A, string &B, int* p, int i, int j, vector<int>& lista) {
	while (j < m) {
		if (A[i] == B[j]) {
			if (i == n - 1) {
				if (s<1000)lista.push_back(j - n + 1);
				s++;
				i = p[i];j++;
			}
			else {	i++;j++; }
		}
		else if (i != 0) i = p[i - 1];
			else j++;
	}
}

int main(){
	ifstream in("strmatch.in");
	string A,B;
	in >> A >> B;

	n = A.length();
	int* p = new int[n];
	p[0] = 0;
	pattern(A,p,1,0);
		
	vector<int>lista;
	m = B.length();
	compare(A, B, p, 0, 0,lista);
	ofstream out("strmatch.out");

	out << s <<"\n";
	for (vector<int>::iterator it=lista.begin();it != lista.end();it++)
		out << *it<<" ";

}