Cod sursa(job #2903475)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 17 mai 2022 16:49:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <cstring>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
 
int lps[2005000];
char c1[2005000];
char c2[2005000];
int x1;
int x2;
int countt;
int rez[1001];
 
void find()
{
  int i=0,j=0;
  while(j<x2)
  {
    if(c1[i]==c2[j])
      i++,j++;
    else if(i!=0)
      i=lps[i-1];
    else
      j++;
    if(i==x1)
    {
      if(countt<1000)
        rez[countt]=j-i;
      countt++;
      i=lps[i-1];
    }
  }
}
 
void createLps()
{
  x1 = strlen(c1);
  x2 = strlen(c2);
  int i=1;
  int len=0;
  for (int k = 1; c1[k] != '\0'; k++)
  {
    do
    {
      if (c1[len] == c1[k])
        break;
      else if (len != 0)
        len = lps[len - 1];
    } while (len != 0);
    if (c1[len] == c1[k])
      len++;
    lps[k] = len;
  }
}
 
int main()
{
  fin.getline(c1,2005000);
  fin.getline(c2,2005000);
  createLps();
  //for(int i=0;i<x1;i++)
  //  std::cout<<lps[i]<<" ";
  find();
  fout<<countt<<"\n";
  for(int i=0;i<countt && i<1000;i++)
    fout<< rez[i]<<" ";
}