Cod sursa(job #2339721)

Utilizator Alexandra06Pribagu Alexandra Alexandra06 Data 9 februarie 2019 11:15:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char s[2000010], t[2000010];
int p[2000010];
int i, m, n, L, sol[1002], aparitii;

int main()
{
  f >> s + 1;
  f >> t + 1;

  n = strlen(s + 1);
  m = strlen(t + 1);

  p[1] = 0;
  L = 0;
  for (i = 2; i <= n; i++)
  {
    while (L != 0 && s[i] != s[L + 1])
          L = p[L];

    if (s[i] == s[L + 1])
        L++;

    p[i] = L;
  }

  L = 0;
  for (i = 1; i <= m; i++)
  {
    while (L != 0 && t[i] != s[L + 1])
          L = p[L];

    if (t[i] == s[L + 1])
        L++;

    if (L == n)
    {
        aparitii++;
        if (aparitii <= 1000)
            sol[aparitii] = i - n;
        L = p[L];
    }
  }

  g << aparitii << '\n';
  if (aparitii > 1000)
      aparitii = 1000;

  for (i = 1; i <= aparitii; i++)
      g << sol[i] << " ";
}