Cod sursa(job #2339606)

Utilizator stefanut999Paul Colta stefanut999 Data 9 februarie 2019 10:20:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s[2000001],t[2000001];

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

  int aparitii = 0,n, m,L,sol[2000001],i,p[2000001];
  n = strlen(s + 1);
  m = strlen(t + 1);

  p[1] = 0;
  L = 0;
  for(i = 2; i <= n; ++i)
    {
      //calculez p[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)
    {
      ///testam potrivire a lui s in t care se termina la pozitia i
      // semnificatia lui L la pasul i = lungimea maxima a unui sufix din t terminat la pozitia i care totodata este prefix de lungime L in s
      while(L != 0 && t[i] != s[L + 1])
        L = p[L];
      if(t[i] == s[L + 1])
        L++;
      if(L == n) //potrivire;
        //fout<<i - n + 1;
        aparitii++;
      if(aparitii <= 1000)
        sol[aparitii] = i - n;
      L = p[L]; // urmatoarea potrivire se poate suprapune cu cea curenta
      //o cautam extinzand prefixul cel mai lung prefix al intregului sir s;

    }
  fout<<aparitii<<'\n';
  int lg = aparitii % 1001;
  for(i = 1; i <= lg; ++i)
    {
      fout<<sol[i]<<' ';
    }
  return 0;
}