Cod sursa(job #1097709)

Utilizator vladutz15FMI Cornoiu Vlad vladutz15 Data 3 februarie 2014 21:11:44
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <cstring>
using namespace std;
#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005
int m,n;
char prim[NMax], secund[NMax];
int urm[NMax], pos[1024];
 
void prefix(void)
{
    int i,q=-1;
    for (i=1;i<m;++i)
    {
        while (q>0 && prim[q+1]!=prim[i])
            q = urm[q];
        if (prim[q+1] == prim[i])
            ++q;
        urm[i] = q;
    }
}
 
int main(void)
{
    int i,q=0,n=0,cont=0;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
	scanf("%s",prim);
	scanf("%s",secund);
	m=strlen(prim);
	n=strlen(secund);
	prefix();
    for (i=0;i<n;++i)
    {       
        while (q>0 && prim[q+1]!=secund[i])
            q = urm[q];
        if (prim[q+1]==secund[i])
            ++q;
        if (q==m-1)
        {
            q=urm[m];
            ++cont;
            if (cont <= 1000)
                pos[cont]=i-m+1;   
        }   
    }       
    printf("%d\n", cont);
    for (i = 1; i <= minim(cont, 1000); ++i)
        printf("%d ", pos[i]);
    printf("\n");
    return 0;
}