Cod sursa(job #2520288)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 9 ianuarie 2020 12:03:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
///strmatch infoarena

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 2000003;

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

int pi[NMAX]; //pi array of word w

int mch=0; //number of matches
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\n%s",w,s);

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

	//make pi vector
	int q=0;
	for(int i=1;i<m;++i){
		while(q && w[i]!=w[q])
			q=pi[q-1];
		if(w[i]==w[q])
			++q;
		pi[i]=q;
	}

	//compare pattern w with string s
	q=0;
	for(int i=0;i<n;++i){
		while(q && s[i]!=w[q])
			q=pi[q-1];

		if(s[i]==w[q])
			++q;

		if(q==m){
			q=pi[q-1];
			mch++;
			poz[i-m+1]=1;
		}
	}

	//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;
}