Cod sursa(job #362500)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 9 noiembrie 2009 21:31:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <cstring>
#define nMax 2000002 
using namespace std;
ifstream f("kmp.in");
ofstream g("kmp.out");

int urm [nMax];
char T[nMax], P[nMax];
int n,m,ap,v[1001];

void citire ()
{
  f.getline (P+1,256); m=strlen (P+1);
  f.getline (T+1,1001); n=strlen (T+1);
  f.close ();
}

void prefix (char *p)
{
  int k=0, x;
  urm[1]=0;
  for (x=2; x<=m; x++)
  {
	while (k>0 && P[k+1]!=P[x]) k=urm[k];
	if (P[k+1]==P[x]) k++;
	urm[x]=k;
  }
}

int main ()
{
  citire ();
  int i, x=0;
  prefix (P);
  for (i=1; i<=n; i++)
  {
	while (x>0 && P[x+1]!=T[i]) x=urm[x];
	if (P[x+1]==T[i]) x++;  //s-au potrivit
	if (x==m)
	{
	  v[++ap]=i-m;
	  x=urm[x];			
	}
  }
  g<<ap<<'\n';
  for (i=1; i<=ap; i++)
    g<<v[i]<<" ";
  g.close (); return 0;
}