Cod sursa(job #1965174)

Utilizator andraSaceliAndra Saceli andraSaceli Data 13 aprilie 2017 23:50:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX=1<<24;
char s[MAX+10];
int pi[MAX+10];
int sol[1020];
int main(int argc, char const *argv[])
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s\n", s + 1) ;
	int n=strlen(s+1);
	scanf("%s", s + n + 2) ;
	s[n+1]='#';
	int m=strlen(s+1);
	//printf("%s\n",s+1);
	//printf("n:%d m:%d \n",n,m);
	for(int i=2; i<=m; ++i)
	{
		int k=pi[i-1];
		while(k and s[k+1]!=s[i])
			k=pi[k];
		if(s[k+1]==s[i])
			++k;
		pi[i]=k;
	}
	int num=0;
	for(int i=n+2; i<=m; ++i)
	{
		//printf("%d ",pi[i]);
		if(pi[i]==n)
		{
			num++;
			if(num<=1000)
				sol[num]=i-n*2-1;
		}
	}
	printf("%d\n",num);
	for(int i=1; i<=num; i++)
	{
		if(i>1000)
			break;
		printf("%d ",sol[i]);
	}
	return 0;
}