Cod sursa(job #143857)

Utilizator DorinOltean Dorin Dorin Data 26 februarie 2008 21:58:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
# include <stdio.h>
# include <cstring>

using namespace std;

# define input "strmatch.in"
# define output "strmatch.out"

# define max 2000002

char a[max],b[max];
int ant[max],n,m,i,q,res[1001],lr;

int main()
{
    freopen(input, "r", stdin);
    freopen(output, "w",stdout);
    
    scanf("%s%s",a,b);
    n = strlen(a);
    m = strlen(b);
    
    for(i=n;i;i--)
      a[i] = a[i-1];
    a[0] = ' ';
    for(i=m;i;i--)
      b[i] = b[i-1];
    b[0] = ' ';
    q = 0;

    for(i = 2;i<=n;i++)
    {
          while(a[q+1]!=a[i] && q)
             q = ant[q];
          if(a[i] == a[q+1])
             q++;
          ant[i] = q;
    }
    
    
    q = 0;
    lr=0;
    for(i=1;i<=m;i++)
    {
       while(q > 0 && b[i] != a[q+1])
           q = ant[q];
       if(a[q+1] == b[i])
                 q = q+1;

       if(q == n)
       {
            q = ant[q];
            lr++;
            if(lr <= 1000)
               res[lr] = i - n;
       }
    }
    printf("%d\n",lr);
    for(i=1;i<=(lr > 1000 ? 1000 : lr);i++)
        printf("%d ",res[i]);
    
    return 0;
}