Cod sursa(job #1309552)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 5 ianuarie 2015 20:38:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
//#include <iostream>
#include <fstream>

using namespace std;

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

#define LE 4000666
#define cout g

int M[LE];
string S,s2;

void Zalg(int n1)
{
    int N=S.length();
    int st=0,dr=0,i;

    for(i=1; i<N; ++i)
    {
        int j=i;

        if (dr>i)
        {
            j+=M[i-st];
            j=min(j,dr);
        }
        for(; j<N&&j-i<n1&&j<N&&S[j]==S[j-i]; ++j)
            bool te=true;

        M[i]=j-i;
        if (j-1>dr&&j-1>=i) st=i,dr=j-1;
    }
}

int main()
{
    f>>S>>s2;
    int N1=S.length();
    int N2=s2.length();
    S+=s2;
    int N=S.length();

    Zalg(N1);
    int nr_sol=0,i;

    for(i=N1; i<N; ++i)
        if (M[i]>=N1)
            ++nr_sol;

    int still=0;

    cout<<nr_sol<<'\n';

    for(i=N1; i<N; ++i)
    {
        if (M[i]<N1) continue;
        cout<<i-N1<<" ";
        ++still;
        if (still==1000) break;
    }

    return 0;
}