Cod sursa(job #504887)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 29 noiembrie 2010 13:16:43
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb

#include <cstdio>

using namespace std;

#define k 2000001

char a[k],b[k];
int p[k],v[1<<10];
int n,m,mn;

void read (){
	
	freopen ("strmatch.in","r",stdin);
	fgets(a, sizeof(a) , stdin);
	fgets(b, sizeof(b) , stdin);
	for(;(a[m]>='A'&&a[m]<='Z')||(a[m]<='z'&&a[m]>='a')||(a[m]>='0'&&a[m]<='9');++m);
	for(;(b[n]>='A'&&b[n]<='Z')||(b[n]<='z'&&b[n]>='a')||(b[n]>='0'&&b[n]<='9');++n);
	for(int i=m;i;--i)
	a[i]=a[i-1];
	a[0]=' ';
	for(int i=n;i;--i)
	b[i]=b[i-1];
	b[0]=' ';
	
	}
			
	void solve (){
		
		int q=0,i;
		for (p[1] = 0,i=2; i <= m; ++i)
	{
		while (q && a[q+1] != a[i])
			q = p[q];
		if (a[q+1] == a[i])
			++q;
		p[i] = q;
	}
		q=0;
		for(i=1;i<=n;++i){
			while(q&&a[q+1]!=b[i])
			q=p[q];
			if(a[q+1]==b[i])
			++q;
			if(q==m){
				q=p[m];
				++mn;
				if(mn<=1000)
				v[mn]=i-m;
				}
			}
		
		}
		
		int inline min (int x,int y){
			
			return (x < y) ? x : y;
			
			}
			
			void write (int kk){
				
				freopen ("strmatch.out","w",stdout);
				printf("%d\n",mn);
				for(int i=1;i<=kk;++i)
				printf("%d ",v[i]);
				printf("\n");
				
				}

int main () 
{
	
	read ();
	solve ();
	write (min(mn,1000));
	
	return 0;}