Cod sursa(job #1317006)

Utilizator BlackBird_v.1.0Stephen Berg BlackBird_v.1.0 Data 14 ianuarie 2015 14:11:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>
using namespace std;
#define Nmax 2000013
string s,s2;
int KMP[Nmax];
int Answer[Nmax];
int main(void)
{
 ifstream cin("strmatch.in");
 ofstream cout("strmatch.out");
 int k=0,sol=0;
 getline(cin,s);
 getline(cin,s2);
 int Sz=s.size();
 s+='#'+s2;
 for (int i=1;i<s.size();++i)
   {
    while(k>0 && s[k]!=s[i]) k=KMP[k-1];
    if (s[k]==s[i]) ++k;
    KMP[i]=k;
   }
 for (int i=Sz+1;i<s.size();++i)
     if (KMP[i]==Sz) 
        Answer[++sol]=i-2*Sz;
        
 cout<<sol<<"\n";
 for (int i=1;i<=sol;++i)
  cout<<Answer[i]<<" ";
 return 0;
}