Cod sursa(job #2382600)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 18 martie 2019 15:26:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 2000010

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

int lps[MAX];
vector<int> ans;
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.push_back(i-j);
      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<<ans.size()<<'\n';
    for(auto i:ans)g<<i<<" ";
    f.close ();
    g.close ();
    return 0;
}