Cod sursa(job #2485842)

Utilizator OvidRata Ovidiu Ovid Data 2 noiembrie 2019 09:56:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 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], m, n;

void computeprefix(){
	pi[1]=0;
	int k=0;
	for(int q=2; q<=m; q++){
		while(k>0 && a[k+1]!=a[q]){k=pi[k];}
		if(a[k+1]==a[q]){k++;}
		pi[q]=k;
	}
}

int kmp(){
    int q=0, res=0;
	for(int i=1; i<=n; i++){
        while(q>0 && a[q+1]!=b[i]){q=pi[q];}

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

		 if(q==m){res++;q=pi[q]; if(res<=1000){c+=to_string(i-m)+" ";}}
         
	}

return res;
}


 


 int main(){
fin>>a>>b;
m=a.length(); n=b.length();
a=" "+a; b=" "+b;

computeprefix();

fout<<kmp()<<endl<<c;

	 return 0;
 }