Cod sursa(job #643240)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 3 decembrie 2011 11:29:00
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#define DN 2000001
#define DN2 10000000
using namespace std;

char a[DN],b[DN];
long long q=1;
vector<int> v;

int main()
{
	int resta=0,restb=0;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w", stdout);
	scanf("%s\n%s",a,b);
	int n=strlen(a);
	int m=strlen(b);
	
	for(int i=0;i<n;i++)
	{
		resta=(resta*27+a[i]-'A'+1)%DN2;
		q=(q*27)%DN2;
		restb=(restb*27+b[i]-'A'+1)%DN2;
	//	cout<<resta<<" "<<restb<<" q:"<<q<<"\n";
		
	}
	
	if(resta==restb)
	{
		v.push_back(1);
	}
	for(int i=n;i<m;i++)
	{
		restb=(restb*27+b[i]-'A'+1)%DN2;
		restb=(restb+-(((b[i-n]-'A'+1)*q)%DN2))%DN2;
		
	//	cout<<restb<<endl;
		if(restb==resta){
			
			v.push_back(i-n+1);
		}
		
	}
	printf("%d\n",v.size());
	for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
	
	return 0;
}