Cod sursa(job #1659759)

Utilizator ris99Istrate Ruxandra ris99 Data 22 martie 2016 16:17:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include<cstring>
using namespace std;
long i,h,n,m,p;
long pi[2000012],v[1024];
char s1[2000012],s2[2000012];
void prefix()
{ int p=0;
  for(i=2;i<=n;i++)
  { while(p&&s1[i]!=s1[p+1]) p=pi[p];
   if(s1[i]==s1[p+1]) p++;
   pi[i]=p;

  }

}
void kmp()
{ p=0;h=0;
  prefix();
  for( i=1;i<=m;i++)
  { while(p&&s2[i]!=s1[p+1]) p=pi[p];
    if(s2[i]==s1[p+1]) p++;
    if(p==n) {h++;p=pi[p];if(h<=1000)v[h]=i-n;}

  }

}
int main()
{ freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  fgets(s1+1,2000010,stdin);
  fgets(s2+1,2000010,stdin);
  n=strlen(s1+1)-1;
  m=strlen(s2+1)-1;
  kmp();
  printf("%ld\n",h);
  if(h>1000) h=1000;
  for(i=1;i<=h;i++)
    printf("%ld ",v[i]);
    return 0;
}