Cod sursa(job #2382605)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 18 martie 2019 15:29:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#define MAX 2000010
#define AMAX 1010

using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int lps[MAX],N;
int ans[AMAX];
string p,s;

void calc_lps(string pat,int* lps){
  lps[0]=0;
  int la=0;
  for(int i=1;i<pat.size();)
    if(pat[i]==pat[la]){
      lps[i]=++la;
      i++;
    } else
      if(la!=0)la=lps[la-1];
      else lps[i++]=0;
}
void rez(string st,string pat){
  calc_lps(pat,lps);
  for(int i=0,j=0;i<st.size();){
    if(st[i]==pat[j])i++,j++;
    if(j==pat.size()){
      ans[++N]=i-j;
      if(N==1000)return;
      j=lps[j-1];
    } else if(i<st.size()&&pat[j]!=st[i]){
      if(j!=0)j=lps[j-1];
      else i++;
    }
  }
}

int main()
{
    f>>p>>s;
    rez(s,p);
    g<<N<<'\n';
    for(int i=1;i<=N;i++)g<<ans[i]<<" ";
    f.close ();
    g.close ();
    return 0;
}