Cod sursa(job #2416574)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 27 aprilie 2019 18:42:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#define MAX 2000010

using namespace std;

int nra;
int lps[MAX],ans[MAX];

string a,b;
void calc_lps(string pat,int lps[MAX]){
  lps[0]=0;
  int la=0;
  for(int i=1;i<pat.size();)
    if(pat[i]==pat[la])lps[i++]=++la;
    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()){
      nra++;
      if(nra<=1000)ans[nra]=i-j;
      j=lps[j-1];
    } else if(i<st.size()&&st[i]!=pat[j]){
      if(j!=0)j=lps[j-1];
      else i++;
    }
  }
}

int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");
    f>>a>>b;
    rez(b,a);
    g<<nra<<'\n';
    for(int i=1;i<=min(1000,nra);i++)g<<ans[i]<<" ";
    f.close ();
    g.close ();
    return 0;
}