Cod sursa(job #790384)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 21 septembrie 2012 08:02:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>
#include<cassert>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

char text[1000005], pat[1000005], aux[1000005];

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

int pi[1000005];

void prefix(){
	pi[1] = 0;
	for(int i = 2; i <= l2; ++i){
		int p = i - 1;
		do{
			
			p = pi[p];
			
			if(pat[i] == pat[p + 1]){
				pi[i] = p + 1;
				break;
			}
			
		}while(p);
		
	}
	
}

vector<int> ans;

int sol[1000005];

void solve(){
	prefix();
	
	for(int i = 1; i <= l1; ++i){
		int p = sol[i - 1];
		
		if (text[i] == pat[p + 1])
			sol[i] = p + 1;
		else
			do{
				p = pi[p];
				if(text[i] == pat[p + 1]){
					sol[i] = p + 1;
					break;
				}
			
			}while(p);
		
			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] - l2); 
	
}

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