Cod sursa(job #1760107)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 20 septembrie 2016 12:23:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<iostream>
#include<string>
#include<fstream>
using namespace std;

string p, t;
int i,j,k,n,prefix[2000005], sol[1005];

int main(void) {
	
	//ifstream cin("strmatch.in");
	//ofstream cout("strmatch.out");
	
	getline(cin,p);
	p=' '+p;
	getline(cin,t);
	t=' '+t;
	
	prefix[0]=-1;
	prefix[1]=0;
	
	for (i=2; i<p.length(); ++i) {
	   
	    k=prefix[i-1];	
		while (k>=0 && p[k+1]!=p[i]) k=prefix[k];
		
		prefix[i]=k+1;
	}
	
	k=0;
	
	for (i=1; i<t.length(); ++i) {
	   
	   while (k>=0 && t[i]!=p[k+1]) k=prefix[k];
	   
	   ++k;
	   
	   if (k==p.length()-1) {
	     
	     ++n;
	     if (n<1000) sol[n]=i-p.length()+1;
	     k=prefix[k];
	   
       }
		
	}
	
	cout<<n<<"\n";
	
	for (i=1; i<=min(n,1000); ++i) cout<<sol[i]<<" ";
	
	return 0;
}