Cod sursa(job #1007383)

Utilizator cahemanCasian Patrascanu caheman Data 8 octombrie 2013 20:59:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<cstring>

using namespace std;

int  vlp[2000002], poz[1002];
char A[2000002],B[2000002];
int lp; // last poz

void prelucrarea(int last)
{
    while(A[lp + 1] != A[last] && lp > 0)
    {
      lp = vlp[lp];
    }
    if(A[lp + 1] == A[last])
      ++ lp;
}

void init(int nA)
{
  int i;
  for(i = 2; i <= nA; ++ i)
  {
    prelucrarea(i);
    vlp[i] = lp;
  }
}

void prelucrareb(int last)
{
    while(A[lp + 1] != B[last] && lp > 0)
    {
      lp = vlp[lp];
    }
    if(A[lp + 1] == B[last])
      ++ lp;
}

int main()
{
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  int i, nA, nB, nrez = 0;
  gets(A + 1);
  nA = strlen(A + 1);
  gets(B + 1);
  nB = strlen(B + 1);
  init(nA);
  lp = 0;
  for(i = 1; i <= nB; ++ i)
  {
    prelucrareb(i);
    if(lp == nA)
    {
      lp = vlp[nA];
      ++ nrez;
      if(nrez <= 1000)
      poz[nrez] = i - nA;
    }
  }
  if(nrez > 1000)
    nrez = 1000;
  printf("%d\n", nrez);
  for(i = 1; i <= nrez; ++ i)
    printf("%d ", poz[i]);
  printf("\n");
  return 0;
}