Cod sursa(job #1029202)

Utilizator taigi100Cazacu Robert taigi100 Data 15 noiembrie 2013 09:46:37
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
/*
   ~Keep It Simple!~
*/

#include<stdio.h>
#include<string.h>

char pat[2000001],str[2000001];
int badmatch[256],rez[1001],cnt;
int n,m;
void bad()
{
	for(int i=0;i<256;i++)
		badmatch[i] = n;
	for(int i=0;i<n-1;i++)
		badmatch[pat[i]] = n - i - 1;
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s %s",pat,str);
	n = strlen(pat);
	m=strlen(str);
	bad();
	int k;
	int i,j; 
	i=j=n;
	while ( i <= m )
	{
		k=i;
		j=n;
		while(j>0 && pat[j-1] == str[k-1] )
		{
			k--;
			j--;
		}
		if(j > 0)
			i+=badmatch[str[k-1]];
		else
		{
			if(cnt < 1000)
				rez[++cnt]=i-n;
			i+=badmatch[pat[n-1]];
		}
	}
	
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
		printf("%d ",rez[i]);
}