Cod sursa(job #2427513)

Utilizator PrekzursilAndrei Visalon Prekzursil Data 31 mai 2019 23:03:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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;
  while(i<x1)
  {
    if(c1[i]==c1[len])
    {
      len++;
      lps[i]=len;
      i++;
    }
    else if(len>0)
      len=lps[len-1];
    else
    {
      len=0;
      lps[i]=0;
      i++;
    }
  }
}
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]<<" ";
}