Cod sursa(job #1996007)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 29 iunie 2017 18:11:52
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
using namespace std;
ifstream fi ("strmatch.in");
ofstream fo ("strmatch.out");
string word,sir;
int i,start,poz,k;
int T[2000004],sol[1006];
void precalc()
{
  int pcuv=1,psuf=0;
  while (pcuv<word.size())
  {
    if (word[pcuv]==word[psuf])
      {
        pcuv++;
        psuf++;
        T[pcuv]=psuf;
      }
    else if (psuf>0) psuf=T[psuf];
    else {pcuv++;T[pcuv]=0;}
  }
  T[0]=0;
  T[1]=1;
}
int main()
{
  fi>>word>>sir;
  precalc();
//  fo<<' '<<word<<'\n';
//  for (i=0;i<word.size();i++) fo<<T[i];
  while (start<=sir.size()-word.size())
    {
      if (poz==word.size()) {k++;sol[k]=start;if (k==1000) break;}
      if (word[poz]==sir[poz+start]) poz++;
      else {start=start+T[poz]+(T[poz]==0);poz=0;}
    }
  fo<<k<<'\n';
  for (i=1;i<=k;i++) fo<<sol[i]<<' ';
  return 0;
}