Cod sursa(job #1097807)

Utilizator vladutz15FMI Cornoiu Vlad vladutz15 Data 3 februarie 2014 22:57:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 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=0;
    for (i=1;i<m;++i)
    {
        while (q>0 && prim[q]!=prim[i])
            q = urm[q-1];
        if (prim[q] == prim[i])
            ++q;
        urm[i] = q;
    }
}
  
int main(void)
{
    int i,q,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();
	q=0;
    for (i=0;i<n;++i)
    {       
        while (q>0 && prim[q]!=secund[i])
            q = urm[q-1];
        if (prim[q]==secund[i])
            ++q;
        if (q==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;
}