Cod sursa(job #2485763)

Utilizator bigmixerVictor Purice bigmixer Data 1 noiembrie 2019 23:20:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
ifstream fin("strmatch.in"); ofstream fout("strmatch.out");

string a, b, c;
int pi[2000005];


void computeprefix(){
pi[0]=0; int k=0;
for(int q=1; q<a.length(); q++){

	if(a[k]!=a[q]){q=0;}
	 if(a[k]==a[q]){k+=1;}
     pi[q]=k;}


}



int kmp(){
int n=0, q=0;
computeprefix();

for(int i=0; i<b.length(); i++){
if(a[q]!=b[i]){q=0;}

if(a[q]==b[i]){q++;}

if(q==a.length()){n++;q=pi[q];  if(n<=1000){c+=to_string(i-a.length()+1)+' '; i+=q-a.length()+1;}}



}

assert(n<=1000);

return n;
}


int main(){
fin>>a>>b;

fout << kmp() << '\n' << c;



	 return 0;
 }