Cod sursa(job #2923510)

Utilizator ezluciPirtac Eduard ezluci Data 15 septembrie 2022 09:17:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int nMAX = 2e6;
const int mMAX = 2e6;

int n, m;
char a[nMAX + 2];
char b[mMAX + 2];
int lps[nMAX + 1];

void buildLPS()
{
   lps[1] = 0;
   int j = 1;
   for (int i = 2; i <= n; ++i)
   {
      if (a[i] == a[j])
         lps[i] = j++;
      else
      {
         lps[i] = lps[i-1];
         j = 1;
      }
   }
}


int main()
{
   fin >> a+1 >> b+1;
   n = strlen(a+1);
   m = strlen(b+1);

   buildLPS();

   vector<int> indici;
   int i = 1;
   for (int j = 1; j <= m; )
   {
      if (a[i] == b[j])
      {
         if (i == n)
         {
            indici.push_back(j-n);
            i = lps[n] + 1;
            j++;
         }
         else
            i++, j++;
      }
      else
      {
         if (i == 1)
            j++;
         else
            i = lps[i-1] + 1;
      }
   }

   fout << indici.size() << '\n';
   for (int x : indici)
      fout << x << ' ';
}