Cod sursa(job #1918108)

Utilizator razvanipRazvan Ispas razvanip Data 9 martie 2017 14:09:26
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<cstring>
using namespace std;
FILE *g=fopen("strmatch.out","w");
char P[2000002],T[2000002];
int pi[2000002];
int a[1001];
int n,m;
void prefix()
{
   // int n,m;
   n=strlen(T);
   m=strlen(P);
   pi[0]=0;
   int k,i;
   k=0;
   for(i=1;i<=m-1;i++)
   {
       while(k>0 && P[i]!=P[k])
       k=pi[k-1];
       if(P[k]==P[i])
        k=k+1;
       pi[i]=k;

   }
}
int main ()
{
    FILE *f=fopen("strmatch.in","r");
    fgets(P,2000000002,f);
   P[strlen(P)-1]=NULL;
    fgets(T,2000000002,f);
    T[strlen(T)-1]=NULL;

  // int n,m;
   n=strlen(T);
   m=strlen(P);
   prefix();
 /*  for(int i=0;i<m;i++)
    fprintf(g,"%d ",pi[i]);
    fprintf(g,"\n");*/

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

   }
   fprintf(g,"%d\n",nr);
   for(int i=1;i<=1000;i++)
    fprintf(g,"%d ",a[i]);
    fclose(f);
    fclose(g);
    return 0;
}