Cod sursa(job #216731)

Utilizator cos_min_max_ionCosmin Ion cos_min_max_ion Data 25 octombrie 2008 15:41:16
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<string.h>
#include<stdio.h>
#define nmax 2000001

int main()
{
 char a[nmax], b[nmax];
 int t[nmax], p[1001],c=0, i,k,pos=2,cnd=0,la,lb;
 freopen("strmatch.in", "rt", stdin);
 freopen("strmatch.out", "wt", stdout);
 gets(a);
 gets(b);
 la=strlen(a);
 lb=strlen(b);
 t[0]=-1;
 t[1]=0;
 while(pos<la)
   {
    if(a[pos-1]==a[cnd])
     {
      t[pos]=cnd+1;
      cnd++;
      pos++;
     }
     else if(cnd>0)
             cnd=t[cnd];
            else
            {
             t[pos]=0;
             pos++;
            }
   }
// for(i=0;i<la;i++)
//    printf("%d ", t[i]);
 i=0;
 k=0;
 while(i<lb)
   {
    while(a[k]!=b[i] && i<lb) i++;
    while(a[k]==b[i+k] && k<la && i+k<lb)
      {
       k++;
      }
    if(k==la)
      {
       p[c++]=i;
       if(c==1000) {break;}
       i+=k-t[k-1]-1;
       k=t[k-1];
      }
      else
        {
         i+=k-t[k];
         k=t[k];
        }
   }
 printf("%d\n", c);
 for(i=0;i<c;i++)
   printf("%d ", p[i]);
 printf("\n");
 return 0;
}