Cod sursa(job #752070)

Utilizator I.AlexandruIlie Alexandru I.Alexandru Data 27 mai 2012 18:56:09
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
#define maxn 2000002
#define maxp 1000
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
int m, n, p[maxn], poz[maxp+128], k=0;
char x[maxn], y[maxn];

inline int minim(int a, int b)
{return (((a)<(b)) ? (a):(b));       
}

inline int is_alphanum(char c)
{return ((c>='A' && c<='Z') || (c>='a' && c<='z') || (c>='0' && c<='9')) ? (1):(0);
}

void make_prefix()
{p[1]=0;
for(int i=2, q=0; i<=m; i++)
   {while(q && x[q+1]!=x[i])
		 q=p[q];
		 
	if(x[q+1]==x[i])
      q++;
	p[i]=q;
   }
}

int main()
{f>>x>>y;

/*
while(is_alphanum(x[m]))
     m++;
     
while(is_alphanum(y[n]))
     n++;
*/

m=strlen(x);
n=strlen(y);
    		
for(int i=m; i; i--) 
   x[i]=x[i-1]; 

for(int i=n; i; i--) 
   y[i]=y[i-1];
   
x[0]=y[0]=' ';	
	
make_prefix();
 	
for(int i=1, q=0; i<=n; i++)
   {while(q && x[q+1]!=y[i])
		 q=p[q];
    
    if(x[q+1]==y[i])
	  q++;
	
    if(q==m)
	  {q=p[m];
	   k++;
	
       if(k<=maxp)
	     poz[k]=i-m;	
	  }	
   }		

g<<k<<"\n";
for(int i=1; i<=minim(k, maxp); i++)
   g<<poz[i]<<" ";
g<<"\n";

return 0;
}