Cod sursa(job #556054)

Utilizator b_ady20Branescu Adrian b_ady20 Data 15 martie 2011 21:45:55
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f; ofstream g;
string a,b; int n,m,t,l[2000005],v[1005];
void prefix(){
	int p,k=0;
	for(p=2,l[1]=0;p<=m;++p){
		while(k&&a[k+1]!=a[p]) k=l[k];
		if(a[k+1]==a[p]) ++k;
		l[p]=k;
	}
}
int main(){
	int j,i=0,k=0;
	f.open("strmatch.in"); g.open("strmatch.out");
	f>>a>>b; 
	m=a.length(); n=b.length();
	for(i=m;i;--i) a[i]=a[i-1]; a[0]=' ';
	for(i=n;i;--i) b[i]=b[i-1];	b[0]=' ';
	prefix();
	for(t=1;t<n;++t){
		while(k&&a[k+1]!=b[t]) k=l[k];
		if(a[k+1]==b[t]) ++k;
		if(k==m){
			++i;
			if(i<=1000) v[i]=t-k;
			k=l[k];
		}
	}
	g<<i<<'\n';
	for(j=1;j<=min(i,1000);++j) g<<v[j]<<' ';
	return 0;
}