Cod sursa(job #1309179)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 5 ianuarie 2015 15:09:34
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
//#include <iostream>
#include <fstream>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");


#include <cstring>

string s,t;
#define LE 5000666
#define cout g

int i,M[LE],j;

void Zalg(int nt)
{
    int N=t.size();
    int st=0,dr=0,i;

    for(i=1; i<N; ++i)
    {
        if (dr>=i) M[i]=M[i-st];

        if (i+M[i]-1>=dr)
        {
            for(j=i+M[i];j-i<nt&& j<N&&t[j-i]==t[j]; ++j);
            M[i]=(j-1)-i+1;
            dr=i+M[i]-1;
            st=i;
        }
    }
}

int main()
{
    f>>s>>t;
    swap(s,t);
    int ns=s.length();
    int nt=t.length();

    t+=s;

   // cout<<t<<'\n';
    int N=t.length();
    Zalg(nt);
    int nr_sol=0;

    int res=0;

    for(i=nt;i<N;++i)
      if (M[i]>=nt) ++res;

    cout<<res<<'\n';

    for(i=nt; i<N; ++i)
    {
        if (M[i]<nt) continue;
        ++nr_sol;
        cout<<i-nt<<" ";
        if (nr_sol==1000) break;
    }
    return 0;
}