Cod sursa(job #696204)

Utilizator BabutaRaresBabuta Rares Mihai BabutaRares Data 28 februarie 2012 17:34:48
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<string.h>
#include<bitset>
using namespace std;
char P[2000001],T[2000001];	
int v[2000001],L[2000001];
int main()
{
	FILE *f=fopen("strmatch.in","r");
	FILE *g=fopen("strmatch.out","w");
	
	char c='0';	
	int k,p,m,i=0,t,n,nr=0;
	fscanf(f,"%c",&c);
	while(c!='\n')
	{				
		P[++i]=c;
		fscanf(f,"%c",&c);
	}
	P[++i]='\0';
	m=i-1;
	
	i=0;
	c='0';
	while(c!='\n')
	{				
		T[++i]=c;
		fscanf(f,"%c",&c);
	}
	n=i-1;
	 L[1] = 0;
     for (p = 2; p <= m; p++) {
       k = L[p-1];
       while (k > 0 && P[k+1] != P[p])
         k = L[k];
       if (P[k+1] == P[p])
         k++;
       L[p] = k; }
	 k = 0;
     for (t = 1; t <= n; t++) {
       while (k > 0 && P[k+1] != T[t])
         k = L[k];
       if (P[k+1] == T[t])
         k++;
       if (k == m) {
		   nr++;
		   v[nr]=t-m-1;		     
         k = L[k]; } }
	 fprintf(g,"%d\n",nr);
	 for(i=1;i<=nr;i++)
		 fprintf(g,"%d ",v[i]);
}