Cod sursa(job #728212)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 28 martie 2012 16:18:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn=2000005;
char t[maxn], p[maxn];
int l,n,m,x,nr;
int urm[maxn];

vector<int>poz;

void urmatorul(char *p)
{
	//urm[k] cate litere din sufixul lui p[0..k] sunt prefixul lui P
	int lung;
	lung=-1;
	//urm[0]=-1;
n=strlen(p);
	for(x=1;x<n;x++) // parcurg prefixele de lungime x  P[0..x]
		{
			
			//cattimp k>0  (lung este cate litere se potrivesc)
			while(lung>0 && p[lung+1]!=p[x])
				lung=urm[lung];       // eu stiu ca am potrivit lung litere din p 
			                  //
				
			if(p[lung+1]==p[x])
				  lung++;
			
			
			urm[x]=lung;
	
		}
}



int cmp(int a, int b)
{
return a>b?0:1;
}


int main()
{
int i;
 int x=-1;

	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
		f.getline(p,maxn);
		   f.getline(t,maxn);

	
	     
			 n=strlen(p);
	 m=strlen(t);
	
	urmatorul(p);

 
	nr=0;
	for(i=0;i<m;i++)
	{
		while(x>0 && p[x+1]!=t[i])
			x=urm[x];
		if(p[x+1]==t[i])    //sirurile s-au potrivit
			x++;
		if(x==n-1)
		{nr++;
		  if(nr<=1000)
			  poz.push_back(i-n+1);
		   
		
		   x=urm[x];
		}
	
	}
	g<<nr<<"\n";
	

	sort(poz.begin(), poz.end(), cmp);
 for(i=0;i<nr &&i<=1000; i++)
	g<<poz[i]<<" ";
	

	
	return 0;
}