Cod sursa(job #2169553)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 14 martie 2018 16:06:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 2000000;

int n, m;

char a[5 + NMAX];
char b[5 + NMAX];

int pi[1 + NMAX];

void prefix()
{
  int k = 0;
  for(int i = 2; i <= n; i++)
  {
    while(k > 0 && a[k + 1] != a[i])
      k = pi[k];

    if(a[k + 1] == a[i])
      k++;

    pi[i] = k;
  }
}

int ct;
int pos[1001];

void solve()
{
  int k = 0;
  for(int i = 1; i <= m; i++)
  {
    while(k > 0 && a[k + 1] != b[i])
      k = pi[k];

    if(a[k + 1] == b[i])
      k++;

    if(k == n)
    {
      ct++;
      if(ct <= 1000)
      {
        pos[ct] = i - n;
      }

      k = pi[k];
    }
  }
}

void output()
{
  printf("%d\n", ct);

  int lim = min(ct, 1000);
  for(int i = 1; i <= lim; i++)
  {
    printf("%d ", pos[i]);
  }
}

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

  scanf("%s%s", a + 1, b + 1);
  n = strlen(a + 1);
  m = strlen(b + 1);

  prefix();
  solve();
  output();

  return 0;
}