Cod sursa(job #1596340)

Utilizator dodecagondode cagon dodecagon Data 10 februarie 2016 22:06:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#include<cstring>
#define min(x,y) x<y ? x:y

char s[2000009],t[2000009];
int n,m,i,j,k,pi[2000009],p[1024];

int main()
{
     freopen("strmatch.in","r",stdin);
     freopen("strmatch.out","w",stdout);

  scanf("%s",&s);
  scanf("%s",&t);
  m=strlen(t);
  n=strlen(s);

  pi[0]=0;
  i=1;j=0;
  while (i<n)
  {
    while (j>0 && s[j]!=s[i])
        j=pi[j-1];
    if (s[j]==s[i]) j++;
    pi[i++]=j;
  }
  k=0;i=0;j=0;
  while (i<m)
  {
    while (j>0 && s[j]!=t[i])
         j=pi[j-1];
    if (s[j]==t[i]) j++;
    if (j==n)
    {
       if (k<1000) p[k]=i-n+1;
       k++;
    }
    i++;
  }
  printf("%d\n",k);
  if (k>1000) k=1000;
  for (i=0;i<k;i++)
    printf("%d ",p[i]);


    return 0;
}