Cod sursa(job #1265052)

Utilizator BLz0rDospra Cristian BLz0r Data 16 noiembrie 2014 17:47:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <cstring>
using namespace std;
 
#define lgmax 2000002
 
FILE *f=fopen ("strmatch.in","r");
FILE *g=fopen ("strmatch.out","w");
 
char a[lgmax],b[lgmax];
int pi[lgmax],sl[1001],sol;
 
void prefix (char s[],int lg){
    int k=0;
     
    for (int i=2;i<=lg;++i){
        while (k>0 && s[i]!=s[k+1]) k=pi[k];
        if (s[i]==s[k+1]) k++;
        pi[i]=k;
    }
}
 
void match (char a[],char b[],int lga,int lgb){
    // lga<lgb
    int k=0;
    for (int i=1;i<=lgb;++i){
        while (k>0 && a[k+1]!=b[i]) k=pi[k];
        if (a[k+1]==b[i]) k++;
        if (k==lga){
            sol++;
            if (sol<=1000) sl[sol]=i-k;
        }
    }
}
 
int main(){
    int lga,lgb;
     
    fscanf (f,"%s%*c",a+1);
    fscanf (f,"%s",b+1);
     
    lga=strlen(a+1);
    lgb=strlen(b+1);
	
	if (lga>lgb){
		fprintf (g,"%d",0);
		return 0;
	}
	
    prefix(a,lga);
    match (a,b,lga,lgb);
	
    int go= sol<=1000?sol:1000;
	
    fprintf (g,"%d\n",sol);
    for (int i=1;i<=go;++i) fprintf (g,"%d ",sl[i]);
     
    return 0;
}