Cod sursa(job #863602)

Utilizator desoComan Andrei deso Data 23 ianuarie 2013 22:25:19
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <vector>
#include <fstream>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;

#define LL long long
#define INFILE "strmatch.in" 
#define OUTFILE "strmatch.out"
#define SMAX 2000010
#define SOLMAX 1024

ifstream fin(INFILE);
ofstream fout(OUTFILE);

string a, b;
int t[SMAX], sol[SOLMAX];

int main() {

   fin >> a >> b;
   int res = 0;

   t[0] = -1;
   int k = 0, n = a.size(), m = b.size();
   for(int j=1; j<n; j++) {
      while( k && a[j]!=a[k] ) k = t[k-1];

      if( a[j]==a[k] ) k++;

      t[j] = k;
   }

   k = 0;
   for(int i=0; i<m; i++) {
      while( k && b[i]!=a[k] ) k = t[k-1];

      if( b[i]==a[k] ) k++;
      if( k==n ) {
         sol[res++] = i-n+1;
         k = t[k-1];
      }

      t[i] = k;
   }

   fout << res << '\n';
   for(int i=0; i<min(res, 1000); i++)
      fout << sol[i] << " ";

   return 0;
}