Cod sursa(job #790066)

Utilizator JohnPeterJohn Peter JohnPeter Data 20 septembrie 2012 09:55:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<cstdio>
#include<cassert>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

int l1, l2;
char text[1000005], pat[10000005], aux[1000005];

void read(){
	
	assert(freopen("strmatch.in", "r", stdin));
	
	gets(aux);
	
	l1 = strlen(aux);
	
	for(int i = 0; i < l1; ++i)
		pat[i + 1] = aux[i];
	
	gets(aux);
	
	l2 = strlen(aux);
	
	for(int i = 0; i < l2; ++i)
		text[i + 1] = aux[i];
	
}

int z[1000005];

void pre(){
	
	int best = 0;
	
	for(int i = 1; i <= l2; ++i){
		
		if(best + z[best] >= i)
			z[i]= min(z[i - best + 1], best + z[best] -i);
		
		while(i + z[i] <= l2 && pat[i + z[i]] == pat[z[i] + 1])
			++z[i];
		
		if(i + z[i] >= best + z[best])
			best = i;
		
	}
	
}

vector<int> ans;
int sol[1000005];

void solve(){
	
	pre();
	
	int best = 0;
	for(int i = 0; i <= l1; ++i){
		
		if(best + sol[best] >= i)
			sol[i] = min(z[i - best + 1], best + sol[best] - i);
		
		while(i + sol[i] <= l2 && sol[i] + 1 <= l1 && text[i + sol[i]] == pat[sol[i] + 1])
			++sol[i];
		
		if(i + sol[i] >= best + sol[best])
			best = i;
		
		if(sol[i] == l2)
			ans.push_back(i);
	}
	
}

void write(){
	
	assert(freopen("strmatch.out", "w", stdout));
	
	printf("%d\n", ans.size());
	
	int lim = ans.size();
	lim = min(lim, 999);
	
	for(int i = 0; i <= lim; ++i)
		printf("%d ",ans[i]);
	
}

int main(){
	read();
	solve();
	write();
	return 0;
}