Cod sursa(job #1106228)

Utilizator radu2004GOLD radu radu2004 Data 12 februarie 2014 17:39:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <string.h>


using namespace std;
FILE *f,*g;
int i,m,n,nr,k,sol[2000002],pi[2000003];
char s1[2000003],s2[2000004];

int main()
{ f=fopen ("strmatch.in","r");
  g=fopen ("strmatch.out","w");
  fgets (s1,2000002,f);
  fgets (s2,2000002,f);
  n=strlen (s1)-1;
  m=strlen (s2)-1;
  k=0;
  for (i=2;i<=n;i++)
  {
     while (k>0 && s1[k]!=s1[i-1])
        k=pi[k];
     if (s1[k]==s1[i-1]) k++;
     pi[i]=k;
  }
  k=0;
  for (i=0;i<m;i++)
  {
      while (k>0 && s1[k]!=s2[i])
        k=pi[k];
      if (s1[k]==s2[i]) k++;
      if (k==n)

            {
                sol[++nr]=i-n+1;
                k=pi[k];
            }

  }
  fprintf (g,"%d\n",nr);
  if (nr>1000) nr=1000;
  for (i=1;i<=nr;i++) fprintf (g,"%d ",sol[i]);
    return 0;
}