Cod sursa(job #2520097)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 8 ianuarie 2020 22:05:15
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

///Possible BASES

//for all uppercase/lowercase letters strings
//#define BASE 31

//for alphabet uppercase+lowercase letters strings
//#define BASE 73

//for alphanumeric strings
//#define BASE 79

//#define BASE 2333


///Possible MODS (you can just use long long overflow => MOD=2^64)

//#define MOD 10007
//#define MOD 10009
//#define MOD 666013
//#define MOD 666019
//#define MOD 1000000007
//#define MOD 1000000009

#define BASE  113
#define MOD1 10007
#define MOD2 10009

const int NMAX = 2000003;///max size of string

char s[NMAX]; //string to be searched
char w[NMAX]; //word to search

int mch=0; //number of pozes
bool poz[NMAX]; //poz[i]=1 => there is a match at position i

int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);


	scanf("%s%s",w,s); //read strings

	int n=strlen(s);
	int m=strlen(w);

	if(m>n){
		printf("0\n");
		return 0;
	}

	int hashw1=0,hashw2=0;
	int hashs1=0,hashs2=0;

	int p1=1,p2=1;

	///make hash for word
	for(int i=0;i<m;++i){
		hashw1=(hashw1*BASE+w[i])%MOD1;
		hashw2=(hashw2*BASE+w[i])%MOD2;
		
		//computing BASE^(m-1) #highest power in hash
		if(i){
			p1=(p1*BASE)%MOD1;
			p2=(p2*BASE)%MOD2;
		}
	}

	//compute hash for initial m characters
	for(int i=0;i<m;++i){
		hashs1=(hashs1*BASE+s[i])%MOD1;
		hashs2=(hashs2*BASE+s[i])%MOD2;
	}

	//check if there is a poz
	if(hashs1==hashw1 && hashs2==hashw2)
		++mch,poz[0]=1;
	
	//compute remaining hashes and check if there is a poz
	for(int i=m;i<n;++i){
		hashs1=((hashs1-(s[i-m]*p1)%MOD1+MOD1)*BASE+s[i])%MOD1;
		hashs2=((hashs2-(s[i-m]*p2)%MOD2+MOD2)*BASE+s[i])%MOD2;

		//check if there is a poz
		if(hashs1==hashw1 && hashs2==hashw2)
			++mch,poz[i-m+1]=1;
	}

	//display
	printf("%d\n",mch);
	int cnt=0;
	for(int i=1;i<n && cnt<1000;++i)
		if(poz[i])
			printf("%d ",i),cnt++;
		
	return 0;
}