Cod sursa(job #2339630)

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

char s[2000010];
char t[2000010];
int sol[1002];
int p[2000010];

int n, m, L, aparitii = 0, i;

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


  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";
       if (aparitii > 1000)
           aparitii = 1000;
       for (i=1;i<=aparitii;i++)
           fout<<sol[i]<<" ";
           return 0;
}