Cod sursa(job #1387655)

Utilizator azkabancont-vechi azkaban Data 14 martie 2015 15:40:40
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
string s,s2;
long long i,j,n,k,sol(0);
long long pi[4000013];
long long V[4000013];
#define minim(a, b) ((a < b) ? a : b)
void kmp()
{
 pi[0]=0;
 for (i=1;i<s.size();++i)
   {
    long long k=pi[i-1];
    while(s[i]!=s[k] && k>0) k=pi[k-1];
    if (s[i]==s[k]) ++k;
    pi[i]=k;
   }
}
  
int main(void)
{
 ifstream  cin("strmatch.in");
 ofstream cout("strmatch.out");
 getline(cin,s);
 getline(cin,s2);
 long long length=s.size();
 s+='#'+s2;
 kmp();
 for (i=length+1;i<s.size();++i)    
   if (pi[i]==length) 
     {
     if (V[0]<=1000) V[++V[0]]=i;
     else ++V[0];
	 }
 cout<<V[0]<<"\n";
 for (i=0;i<minim(V[0],1000);++i)
    cout<<V[i]<<" ";    
 return 0;
}