Cod sursa(job #1410649)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 31 martie 2015 10:43:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
//#include <iostream>

#include <fstream>


using namespace std;

#define LE 4000666
#define cout g

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


int prf[LE];
string a,s1,s2;

void solve(int N)
{
    int st=-1,dr=-1,i;

    for(i=1; i<N; ++i)
    {
        if (i==8)
          bool okz=true;

        if (dr<=i)
        {
            int j=i;
            while (a[j]==a[j-i]&&j<N)
              ++prf[i],++j;
            if (prf[i]<=1) continue;
            st=i,dr=i+prf[i]-1;
            continue;
        }

        int l=prf[i-st];

        if (l+i-1<dr)
        {
            prf[i]=l;
            continue;
        }

        int j=min(i,dr-1);

        while (a[j]==a[j-i]&&j<N) ++j;
        prf[i]=(j-i);
        st=i,dr=j-1;
    }
}


int main()
{
    f>>s1>>s2;
    a=s1+s2+" ";
    int N=a.size();
    int i;

    solve(N);

   // for(i=0;i<N;++i) cout<<prf[i]<<" ";

   // cout<<'\n'<<'\n';

    int n1=s1.size();
    int nr_sol=0;

    for(i=n1; i<N; ++i)
    {
        if (prf[i]<n1) continue;
        ++nr_sol;
    }

    int nrc=0;

    cout<<nr_sol<<'\n';

    for(i=n1; i<N; ++i)
    {
        if (prf[i]<n1) continue;
        ++nrc;
        if (nrc>1000) break;
        cout<<i-n1<<" ";
    }

    return 0;
}