Cod sursa(job #1966506)

Utilizator andraSaceliAndra Saceli andraSaceli Data 15 aprilie 2017 12:30:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <cstring>
using namespace std;
const unsigned int BASE=197;
const int MAX=1<<21|1;
char s[MAX];
unsigned int put[MAX];
unsigned int h[MAX];
int sol[1005];
int main(int argc, char const *argv[])
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s\n",s);
	int n=strlen(s);
	unsigned int val=0;
	for(int i=n-1; i>=0; --i)
		val=val*BASE+s[i];
	scanf("%s",s);
	int n2=strlen(s);
	put[0]=1;
	for(int i=1; i<=n2; ++i)
		put[i]=put[i-1]*BASE;
	for(int i=n2-1; i>=0; --i)
		h[i]=h[i+1]*BASE+s[i];
	int num=0;
	for(int i=0; i<n2; ++i)
	{
		int j=i+n-1;
		if(j>=n2)
			break;
		if(val==h[i]-h[j+1]*put[j-i+1])
		{
			++num;
			if(num<=1000)
				sol[num]=i;
		}
	}
	printf("%d\n",num);
	for(int i=1; i<=1000; ++i)
	{
		if(i>num)
			break;
		printf("%d ",sol[i]);
	}
	return 0;
}