Cod sursa(job #723417)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 25 martie 2012 14:32:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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 >> A;
 long la,lb,i,j,c;
 la = strlen(A);
 lb = strlen(B);

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

/* j = -1;
 prefix[0] = 0;
 for (i = 1;i < la;i += 1)
  {
   while ((j >= 0) && (A[j] != A[i]))
    {
     j = prefix[j];
    }
   if (A[j] == A[i])
     {
      j += 1;
     }
   prefix[j]
  }*/

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