Cod sursa(job #1996017)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 29 iunie 2017 18:25:22
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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;
  T[0]=-1;
  while (pcuv<word.size())
  {
    if (word[pcuv]==word[psuf])
      {
        T[pcuv]=T[psuf];
        pcuv++;
        psuf++;
      }
    else
    {
      T[pcuv]=psuf;
      while (psuf>0 and word[pcuv]!=word[psuf]) psuf=T[psuf];
      pcuv++;psuf++;
    }
  }
}
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;start++;poz=0;}
      if (word[poz]==sir[poz+start]) poz++;
      else if (poz>0) {start=start+poz-T[poz];poz=T[poz];}
      else {start=start+poz+1;poz=0;}
    }
  fo<<k<<'\n';
  for (i=1;i<=k;i++) fo<<sol[i]<<' ';
  return 0;
}