Cod sursa(job #568609)

Utilizator david_raucaRauca Ioan David david_rauca Data 31 martie 2011 15:11:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[2000001];
char B[2000001];

int t[2000001];

void KMP();

int main()
{
    fin >> A+1;
    fin >> B;
    
    KMP();
    
    fin.close();
    fout.close();
    
    return 0;
}

void KMP()
{
     t[1] = 0;
     int n = strlen(A+1);
     int pos = 0;
     for( int i = 2; i <= n; ++i )
     {
          while( pos > 0 && A[pos+1] != A[i] )
                 pos = t[pos];
          
          if( A[pos+1] == A[i] )
              pos++;
          
          t[i] = pos;
     }
     
     //for( int i = 1; i <= n; ++i )
     //     fout << t[i] << ' ';
     int m = strlen(B);
     pos = 0;
     vector<int> pozitii;
     for( int i = 0; i < m; ++i )
     {
          while( pos > 0 && A[pos+1] != B[i] )
                 pos = t[pos];
          if( A[pos+1] == B[i] )
              pos++;
          
          if( pos == n )
          {
              pos = t[pos];
              pozitii.push_back(i-n+1);
          }
     }
     
     int z = pozitii.size();
     fout << z << '\n';
     if( z > 1000 )
         z = 1000;
     for( int i = 0; i < z; ++i )
          fout << pozitii[i] << ' ';
}