Cod sursa(job #2000297)

Utilizator epermesterNagy Edward epermester Data 13 iulie 2017 12:57:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <string>
#include <deque>
using namespace std;

int n, m, s=0;

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

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

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

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

	out << s <<"\n";
	for (int i = 0;i<s && i<1000;++i) {
		out << lista.front()<<" ";
		lista.pop_front();
	}
}