Cod sursa(job #505656)

Utilizator adalLica Adela adal Data 3 decembrie 2010 15:02:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <string.h>
#define Max 2000002
#include <algorithm>

using namespace std;

char T[Max], P[Max];
int n, m, L[Max], a[1002];

void prefix(){
 int i,k;
  L[1]=0;
  for (i=2; i<=n; i++){
    k=L[i-1];
	while (k>0 && P[i]!=P[k+1]) k=L[k];
    if (P[i]==P[k+1]) k++;
	L[i]=k;
  }

}

void match()
{
 int k, nr, i;
 k=0; nr=0;
 for (i=1; i<=m; i++){
   while (k>0 && T[i]!=P[k+1]) k=L[k];
   if (T[i]==P[k+1])
	    k++;
   if (k==n)
    {
		nr++;
		if (nr<=1000) 
			a[nr]=i-n;
		k=L[n];
    }
 }

  printf("%d\n", nr);
  for (i=1;i<=min(1000,nr); i++) printf("%d ",a[i]);
  printf("\n");  
}

int main()
{
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  fgets(P+1, Max, stdin);  fgets(T+1, Max, stdin);
  n=strlen(P+1)-1; m=strlen(T+1)-1;
  prefix();
  match();
  return 0;
  }