Cod sursa(job #2490163)

Utilizator DavidTurtureanCDavid Turturean DavidTurtureanC Data 9 noiembrie 2019 20:23:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[4000005],t[2000005]; int n,len,lps[4000002],i,lens,lent,nr;
int main(){
  fin>>s>>t; lens=strlen(s); lent=strlen(t);
  strcat(s,"#"); strcat(s,t); n=lens+lent+1;
  len=lps[0]=0; i=1;
  while(i<n){
     if(s[i]==s[len]) {lps[i++]=++len; if(lps[i-1]==lens && i>=lens+1)nr++;}
     else{
      if(len)len=lps[len-1];
      else lps[i++]=0;
     }
  }
  fout<<nr<<'\n';
  for(i=lens+1;i<lens+1+lent;i++)if(lps[i]==lens)fout<<i-2*lens<<" ";
    return 0;
}