Cod sursa(job #1516598)

Utilizator MarcSpataruMarc Spataru MarcSpataru Data 3 noiembrie 2015 11:03:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int n1=100007,n2=100021,lmax=2000000;
char s1[lmax],s2[lmax];
int v[1001];
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	int nr1s2,nr2s2,i,k1,k2,nr1s1,nr2s1;
	scanf("%s",&s2);
	scanf("%s",&s1);
	k1=strlen(s1);k2=strlen(s2);
	nr1s2=nr2s2=0;
	for(i=0;i<k2;i++)
	{
		nr1s2=((nr1s2*123)%n1+s2[i])%n1;
		nr2s2=((nr2s2*123)%n2+s2[i])%n2;
	}
	for(i=0;i<k1;i++)
	{
		nr1s1=((nr1s1*123)%n1+s2[i])%n1;
		nr2s1=((nr2s1*123)%n2+s2[i])%n2;
	}
	int p1=1,p2=pow(123,k2-1),j,k,poz=0;
	bool pp=true;
	nr1s1=nr2s1=0;
	for(j=0;j<k1-k2;j++)
	{
		nr1s1-=s2[j]*p1;
		nr2s1-=s2[j]*p1;
		nr1s1%=n1;
		nr2s1%=n2;
		while(nr1s1<0)
			nr1s1+=n1;
		while(nr2s1<0)
			nr2s1+=n2;
		p1*=123;p1%=n1;
		nr1s1+=s2[j+k2]*p2;
		nr2s1+=s2[j+k2]*p2;
		while(nr1s1<0)
			nr1s1+=n1;
		while(nr2s1<0)
			nr2s1+=n2;
		p2*=123;p2%=n1;
		if(nr1s2!=nr1s1||nr2s2!=nr2s1)
		{
			pp=false;
		}
		else
		{
			v[++poz]=j;
		}
	}
	printf("%d\n",poz);
	for(i=1;i<=poz;i++)
	{
		printf("%d ",v[i]);
	}
	return 0;
}