Cod sursa(job #1219568)

Utilizator azkabancont-vechi azkaban Data 14 august 2014 16:40:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstring>
#include <cstdio>
#define maxN 2000013
char S1[maxN], S2[maxN];
int Pi[maxN], d[maxN];
int i,k(0),A,B,sol(0);

void build_pi()
{
 int k(0),N(strlen(S1)-1),i; 
 Pi[1]=0;
 for (i=2;i<=N;++i){
                    while (k>0 && S1[i]!=S1[k+1]) k=Pi[k];
                    if (S1[i]==S1[k+1]) ++k; 
                    Pi[i]=k;     
                   }
}
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 fgets(S1+1,maxN,stdin);
 fgets(S2+1,maxN,stdin);
 S1[0]=S2[0]=' ';
 S1[strlen(S1)-1]=S2[strlen(S2)-1]=0;
 A=strlen(S1)-1;
 B=strlen(S2)-1;
 build_pi();
 for (i=1;i<=B;++i){
                    while (k>0 && S2[i]!=S1[k+1]) k=Pi[k]; 
                    if (S2[i]==S1[k+1]) ++k; 
                    if (k==A){
                              k=Pi[A];
                              ++sol;
                              if (sol<=1000) d[sol]=i-A;
                              }
                   }
 printf("%d\n",sol);
 for (i=1;i<=sol;++i)
     printf("%d ",d[i]);
 return 0;
}