Cod sursa(job #2520363)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 9 ianuarie 2020 12:57:51
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
//strmatch infoarena

#include <cstdio>
#include <cstring>

using namespace std;

const int NMAX = 2000003;

char s[NMAX];//string
char w[NMAX];//pattern

int z[NMAX]; //z[i] length of segment starting at position i that is the same as the preffix of the string

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

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

	scanf("%s%s",w,s);

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

	for(int k=1,st=0,dr=0; k<n; ++k){
		if(k>dr){
			st=dr=k;
			while(dr<n && s[dr]==w[dr-st])
				++dr;
			z[k]=dr-st;
			dr--;
		}else{
			if(k+z[k-st]<=dr)
				z[k]=z[k-st];
			else{
				st=k;
				while(dr<n && s[dr]==w[dr-st])
					++dr;
				z[k]=dr-st;
				dr--;
			}
		}
		if(z[k]==m){
			++mch;
			poz[k]=1;
		}
	}


	/*
	for(int k=1,st=0,dr=0; k<l; ++k){
		if(k>dr){//if im ahead of current preffix
			st=dr=k;
			while(dr<l && w[dr]==w[dr-st])
				++dr;
			z[k]=dr-st;
			dr--;
		}else{ //if im inside preffix
			if(k+z[k-st]<=dr) //checking if preffix goes over boundaries, if it doesn't just copy z
				z[k]=z[k-st];
			else{ //otherwise we try to expand
				st=k;
				while(dr<l && w[dr]==w[dr-st])
					++dr;
				z[k]=dr-st;
				dr--;
			}
		}
	}
*/
	

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