Cod sursa(job #2221431)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 14 iulie 2018 11:47:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<cstring>
using namespace std;

string a,b;
int n,m,nrm, prefix[2000005];
bool match[2000005];


void build_prefix() {
  
   for (int i=1; i<n; ++i) {
      int k=prefix[i-1];
      
      while (k>0 && a[i]!=a[k]) k=prefix[k-1];
      
      if (k==0 && a[i]==a[0]) prefix[i]=1;
      else if (k>0) prefix[i]=k+1;
   
   }
	
}

int main(void) {
   ifstream cin("strmatch.in");
   ofstream cout("strmatch.out");
   
   getline(cin,a);
   getline(cin,b);
   
   n=a.length();
   m=b.length(); 
   
   build_prefix();
   
   int idx=0;
   
   for (int i=0; i<m; ++i) {
   
      if (b[i]==a[idx]) ++idx;
      else {
	     while (idx>0 && b[i]!=a[idx]) idx=prefix[idx-1];
      
         if (b[i]==a[idx]) ++idx;
     }
     
     if (idx==n) {
     	++nrm;
     	match[i-n+1]=1;
     	idx=prefix[n-1];
     }
   
   } 
   
   cout<<nrm<<"\n";
   
   int cnt=1000;
   for (int i=0; i<m && cnt>0; ++i)
    if (match[i]==1) {
       cout<<i<<" ";
	   --cnt;	
    }
		
   return 0;
}