Cod sursa(job #1651989)

Utilizator rudarelLup Ionut rudarel Data 14 martie 2016 13:13:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <string.h>
#define MAX 2000001

using namespace std;
 
char a[MAX], b[MAX];
int n, m, p[MAX], nr, sol[1001];
 
int main()
{
	int i = 0, k = 0;
	freopen("strmatch.in","r",stdin);
  	freopen("strmatch.out","w",stdout);
  	a[0]=b[0] = ' ';
 	scanf("%s",a+1); n = strlen(a);
	scanf("%s",b+1); m = strlen(b);
  	for(i = 2; i <= n; i++)
  	{
  		while(k && a[k+1] != a[i]) k = p[k];
  		if(a[k+1] == a[i]) k++;
  		p[i] = k;
	}
	k = 0;
	for(i = 1; i <= m; i++)
	{
		while(k && a[k+1] != b[i]) k = p[k];
		if(a[k+1] == b[i]) k++;
		if (k == n - 1)
		{
			nr++;
			if(nr <= 1000) sol[nr] = i - n + 1;
		}
	}
	printf("%d\n",nr);
  	if(nr > 1000) nr = 1000;
    for(i = 1;i <= nr; i++) printf("%d ",sol[i]);
  	return 0;
}