Cod sursa(job #871790)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 5 februarie 2013 11:26:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#include<cassert>
#include<cstring>

#include<vector>
#include<algorithm>

using namespace std;

char a[2000005], b[2000005];
int l1, l2, p[2000005];

void read(){
	assert(freopen("strmatch.in", "r", stdin));
	
	gets(a);
	gets(b);
	
	l1 = strlen(a);
	l2 = strlen(b);
	for(int i = l1; i > 0; --i)
		a[i] = a[i - 1];
	for(int i = l2; i > 0; --i)
		b[i] = b[i - 1];
}

void pref(){
	p[1] = 0;
	
	for(int i = 2; i <= l1; ++i){
		int t = i - 1;
		
		do{
			t = p[t];
			
			if(a[t + 1] == a[i]){
				p[i] = t + 1;
				break;
			}
		}while(t);
		
	}
	
}

int ans, d[2000005];
vector<int> v;

void solve(){
	pref();
	
	for(int i = 1; i <= l2; ++i){
		int t = d[i - 1];
		
		if(a[t + 1] == b[i])
			d[i] = t + 1;
		else do{
			t = p[t];
			
			if(a[t + 1] == b[i]){
				d[i] = t + 1;
				break;
			}
		}while(t);
		if(d[i] == l1){
			++ans;
			if(ans <= 1000)
				v.push_back(i - l1);
		}
	}
}

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

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