Cod sursa(job #2937644)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 10 noiembrie 2022 19:21:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2000005;

int lps[nmax];
int res[1005];
int ind = 0;
string pattern, text;

void calcKMP()
{
  int l = 0;
  lps[0] = 0;
  int i = 1;
  while (i < pattern.size())
  {
    if (pattern[l] == pattern[i])
    {
      lps[i++] = ++l;
    }
    else
    {
      if (l)
      {
        l = lps[l - 1];
      }
      else
      {
        lps[i++] = 0;
      }
    }
  }
  l = i = 0;
  while ((text.size() - i) >= (pattern.size() - l))
  {
    if (pattern[l] == text[i])
    {
      i++;
      l++;
    }
    if (l == pattern.size())
    {
      res[ind++] = i - l;
      l = lps[l - 1];
    }
    else
    {
      if (i < text.size() && pattern[l] != text[i])
      {
        if (l)
          l = lps[l - 1];
        else
          i++;
      }
    }
  }
}

int main()
{
  in >> pattern >> text;
  calcKMP();
  out << ind << '\n';
  for (int i = 0; i < min(ind, 1000); i++)
  {
    out << res[i] << ' ';
  }
}