Cod sursa(job #2490219)

Utilizator DavidTurtureanCDavid Turturean DavidTurtureanC Data 9 noiembrie 2019 22:06:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 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,contor;
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 && contor<=999;i++)if(lps[i]==lens){fout<<i-2*lens<<" ";contor++;}
    return 0;
}