Cod sursa(job #676711)

Utilizator rusu_raduRusu Radu rusu_radu Data 9 februarie 2012 15:43:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define Nmax 2000005
#define InFile "strmatch.in"
#define OutFile "strmatch.out"

using namespace std;

int n, m, q;
int L[Nmax], pz[1005];
char T[Nmax], P[Nmax];

void read();
void prefix();
void solve();
void write();

int main()
{
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  prefix();
  solve();
  write();
  return 0;
}

void read()
{
  scanf ("%s\n", P+1);
  m=strlen (P+1);
  scanf ("%s\n", T+1);
  n=strlen (T+1);
}

void prefix()
{
  int i, k;
  L[1]=0;
  for (i=2; i<=m; i++)
  {
    k=L[i-1];
    while (k>0 && P[k+1]!=P[i])
      k=L[k];
    if (P[k+1]==P[i])
      k++;
    L[i]=k;
  }
}

void solve()
{
  int i, k;
  k=L[1];
  for (i=1; i<=n; i++)
  {
    while (k>0 && P[k+1]!=T[i])
      k=L[k];
    if (P[k+1]==T[i])
      k++;
    if (k==m)
    {
      if (q<1000)
        pz[q]=i-k;
      q++;
      k=L[k];
    }
  }
}

void write()
{
  int i;
  printf ("%d\n", q);
  for (i=0; i<min (q, 1000); i++)
    printf ("%d ", pz[i]);
  printf ("\n");
}