Cod sursa(job #169871)

Utilizator stinkyStinky si Grasa stinky Data 2 aprilie 2008 08:51:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<string.h>

#define N 2000007

int p[N], m, n, sol[1005], nr;
char a[N], b[N];

void init_p(){//stabileste pentru fiecare pref, [q], care e lung celui mai mare pref [k],care e suf pt el (k<q)
	int k=0,q;
	m=strlen(a+1);
	n=strlen(b+1);
	p[1]=0;
	for(q=2; q<=m; ++q){
		while(k && a[k+1]!=a[q])//incerc toate sufixele lui [q-1] (incerc sa adaug un caracter)
			k=p[k];//parcurg pref care sunt suf ale lui [q-1]
		if(a[k+1]==a[q])//daca am gasit sufix
			++k;//acest sufix are lungimea mai mare cu 1 decat sufixul lui [q-1] la care-l adaug
		p[q]=k;
	}
}

void kmp(){
	int i,q=0;
	for(i=1; i<=n ;++i){
		while(q && a[q+1]!=b[i])//incerc toate pref care au ultimul car=b[i-1] (suf ale celui de la pasul i-1)
			q=p[q];//parcurg pref care au ultimul car b[i-1] (pref ale celui pe care l-am ales inainte)
		if(a[q+1]==b[i])//daca am gasit un pref [q] cu ult car b[i-1] si care are a[q+1]=b[i], 
			++q;//atunci [q+1] este pref cel mai mare al lui a care are ult car=b[i]
		if(q==m){
			if(nr<1000)
				sol[nr++]=i-m+1;
			else
				++nr;
		}
	}
}

void citire(){
	scanf("%s\n%s",a+1,b+1);
}

void scrie(){
	printf("%d\n",nr);
	int min = (nr < 1000 ? nr : 1000);
	for(int i=0; i<min-1; ++i)
		printf("%d ",sol[i]-1);
	if(min)
		printf("%d\n",sol[min-1]-1);
}

int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	citire();
	init_p();
	kmp();
	scrie();
	return 0;
}