Cod sursa(job #723482)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 25 martie 2012 15:06:40
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb

#include <fstream>
#include <string.h>
using namespace std;

char A[2000005];
char B[2000005];
char prefix[2000005];
long res[1024];

int main(void)
{
 fstream fin("strmatch.in",ios::in);
 fstream fout("strmatch.out",ios::out);
 fin >> (B + 1) >> (A + 1);
 long la,lb,i,j,c;
 la = strlen(A + 1);
 lb = strlen(B + 1);

 c = 0;

 j = 0;
 prefix[1] = 0;
 for (i = 2;i <= lb;i += 1)
  {
   while ((j > 0) && (B[j + 1] != B[i]))
    {
     j = prefix[j];
    }
   if (B[j + 1] == B[i])
     {
      j += 1;
     }
   prefix[i] = j;
  }

 j = 0;
 for (i = 1;i <= la;i += 1)
  {
   while ((j > 0) && (B[j + 1] != A[i]))
    {
     j = prefix[j];
    }
   if (B[j + 1] == A[i])
    {
     j += 1;
    }
   if (j == lb)
     {
      j = prefix[lb];
      if (c < 1000)
        {
         res[c] = i - lb;
        }
      c += 1;
     }
  }

 fout << c << "\n";
 if (c > 1000)
   {
    c = 1000;
   }
 for (i = 0;i < c;i += 1)
  {
   fout << res[i] << " ";
  }
 fin.close();
 fout.close();
 return 0;
}