Cod sursa(job #338634)

Utilizator prdianaProdan Diana prdiana Data 6 august 2009 12:57:56
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

int p[256];
vector<int> sol;

int main()
{
	char a[2000002],b[2000002];
	int la,lb,i,l,cp;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	scanf("%s",&a);
	scanf("%s",&b);
	la = strlen(a);
	lb = strlen(b);

	for (i=la-2;i>=0;i--)
	{
		if (p[a[i]] == 0)
		{
			p[a[i]] = la - i-1;
		}
	}
	for (i=0;i<256;i++)
	{
		if (p[i] == 0)
		{
			p[i] = la;
		}
	}

	i = la;
	cp = la;
	l = 0;
	while (i<lb)
	{
		if (a[la-l-1] == b[i])
		{
			i--;
			l++;
		}
		else
		{
			l = 0;
			cp++;
			i = cp;
		}
		if (l == la)
		{
			if (sol.size()<1000)
			{
				sol.push_back(i+1);
			}
			cp++;
			i = cp;
		}


	}
	printf("%d\n",sol.size());
	for (i=0;i<sol.size();i++)
	{
		printf("%d ",sol[i]);
	}
	return 0;
}