Cod sursa(job #1004767)

Utilizator tester6669testeru testreru tester6669 Data 3 octombrie 2013 17:18:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <iostream>
using namespace std;

#define LE 500666
ifstream f("strmatch.in");
ofstream g("strmatch.out");

#include <cstring>
string s1,s2;

int n,a[LE];
int i,j,prfx[LE];
int main()
{
	//f>>n;
	//for(i=1;i<=n;++i) f>>b[i];
	//for(i=2;i<=n;++i) a[i-1]=b[i]-b[i-1];
	
	int st=0,dr=0;
	//--n;
	
	//for(i=1;i<=n;++i) cout<<a[i]<<" ";
	//cout<<'\n';
	f>>s1>>s2;
	int n1=s1.length();
	s1+=s2;
	n=s1.length();
	int result=0;
	
	for(i=0;i<n;++i) a[i+1]=s1[i];
//	cout<<s1<<'\n';
	
	
	//for(i=1;i<=n;++i) cout<<a[i]-'A'<<" ";
	//cout<<'\n';
	
	for(i=2;i<=n;++i)
	{
	    if (dr>=i)
		{
			
		   int pos=i-st+1;
		  
	       if (prfx[pos]+i<=dr) 
	  	   {
			   prfx[i]=prfx[pos];
		 	   continue;
		   }
		}
		if (dr<i) dr=i;
		
		for(j=dr;j<=n&&a[j]==a[j-i+1];++j);
		
		st=i;
		dr=j-1;
		
		prfx[i]=dr-st+1;
//	    cout<<prfx[i]<<" "<<dr<<'\n';
		if (i>=n1+1&&prfx[i]>=n1) ++result;
	}
	
//	for(i=1;i<=n;++i) cout<<prfx[i]<<" ";
	
	cout<<result<<'\n';
	int nr=0;
	
	for(i=n1+1;i<=n;++i) 
		 if (prfx[i]>=n1&&nr<2000) 
		 {
			cout<<i-n1-1<<" ";
		    ++nr;
		 }
	
	
    f.close();
	g.close();
	return 0;
}