Cod sursa(job #1478763)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 29 august 2015 14:46:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <string>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string a,b;
int n, alen;
int zFunction[4000000];

int leftLimit, rightLimit;

int main(void){
	
	in >> a;
	in >> b;
	alen = a.length();
	a += "#"+b;
	n =a.length();
	leftLimit = 0;rightLimit = 0;
	for (int i=1;i<n;i++){
		if (i<=rightLimit) zFunction[i] = min(zFunction[i-leftLimit], rightLimit-i+1);
		while(i+zFunction[i]<n && a[i+zFunction[i]]==a[zFunction[i]]) zFunction[i]++;
		if(i+zFunction[i]-1>rightLimit){
			leftLimit = i;
			rightLimit = i+zFunction[i]-1;
		}
	}
	
	int count=0;
	for (int i=0;i<n;i++){
		if (zFunction[i]==alen)count++;
	} 
	out << count << "\n";
	count = 0;
	for (int i=0;i<n && count<1000;i++) 
		if (zFunction[i]==alen){
			out << i-alen-1 << " ";
			count++;
		}
	
	out << "\n";
	return 0;
}