Cod sursa(job #1219626)

Utilizator azkabancont-vechi azkaban Data 14 august 2014 18:02:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <string>
#define maxN 4000050
#define minim(a, b) ((a < b) ? a : b)
using namespace std;
string S1,S2;
int Pi[maxN],Answer[maxN];
int i,A,B,sol,k(0);
int main()
{
 ifstream cin("strmatch.in");
 ofstream cout("strmatch.out");
 getline(cin,S1); 
 getline(cin,S2);
 A=S1.size();
 S1+='#'+S2;
 Pi[0]=0;
 for (i=1;i<S1.size();++i)
              {
               while (k>0 && S1[i]!=S1[k]) k=Pi[k-1]; 
               if (S1[i]==S1[k]) ++k; 
               Pi[i]=k;
               }
 for (i=A+1;i<=S1.size()-1;++i)
     if (Pi[i]==A) 
        Answer[++sol]=i-2*A;
 cout<<sol<<"\n";
 for (i=1;i<=min(sol,1000);++i)
 cout<<Answer[i]<<" ";
 return 0;
}