Cod sursa(job #365709)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 noiembrie 2009 18:46:05
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<iostream>
#include<string>

using namespace std;

#define LM 2000005
#define FOR(i,a,b)for(i=(a);i<=(b);++i)

int sl,tl,pi[LM],dim,pozitii[1005];

char S[LM],T[LM];

void get_pi()
{
    int how_many=0,i; 
     
    pi[0]=0;
    
    FOR(i,1,sl-1)
    {
      while(how_many && S[how_many]!=S[i]) how_many=pi[how_many];
      
      if(S[how_many]==S[i]) ++how_many;
      
      pi[i]=how_many;
    }
}

inline void new_occurence(int pos)
{
     //printf("%d\n",pos);
     
     ++dim;
     if(dim<=1000) pozitii[dim]=pos;
}

void get_kmp()
{
     int how_many=0,where=0;
     
     while(where<tl)
     {
       while(how_many && S[how_many]!=T[where]) how_many=pi[how_many];
       
       if(S[how_many]==T[where]) ++how_many;
       
       if(how_many==sl)
       {
         new_occurence(where-sl+1);
         how_many=pi[how_many];
       }  
       
       ++where;
     }
}

int main()
{
    int i;
    
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    scanf("%s",&S);
    scanf("%s",&T);
    
    sl=strlen(S);
    tl=strlen(T);
    
    get_pi();
    
    get_kmp();
    
    printf("%d\n",dim);
    
    FOR(i,1,dim)
      printf("%d ",pozitii[i]);
      
    return 0;
}