Cod sursa(job #1212436)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 24 iulie 2014 17:55:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char a[2000010],b[2000010];
int z[2000010],pr[1010],cnt,t;

void calc_z ()
{
    z[1] = 0;
    int L = 0, R = 0, n = strlen (a+1);

    for (int i=2; i <= n; ++i)
    {
        if (i > R)
        {
            int j=1;
            L = i;
            R = i;

            while (R <= n && a[R] == a[j])
            {
                ++j;
                ++R;
            }

            --R;
            z[i] = j-1;
        }
        else
        {
            if (z[i-L+1] < R-i+1)
              z[i] = z[i-L+1];
            else
            {
                int j = R-i+1;
                L = i;

                while (R <= n && a[R] == a[j])
                {
                    ++j;
                    ++R;
                }

                --R;
                z[i] = j-1;
            }
        }
    }
}

void solve ()
{
    int L = 0, R = 0, n = strlen (b+1), na = strlen (a+1);

    for (int i=1; i<=n; ++i)
    {
        int ans = 0;

        if (i > R)
        {
            int j = 1;
            L = i;
            R = i;

            while (R <= n && b[R] == a[j])
            {
                ++j;
                ++R;
            }

            --R;
            ans = j-1;
        }
        else
        {
            if (z[i-L+1] < R-i+1)
              ans = z[i-L+1];
            else
            {
                int j = R-i+1;
                L = i;

                while (R <= n && b[R] == a[j])
                {
                    ++j;
                    ++R;
                }

                --R;
                ans = j-1;
            }
        }

        if (ans == na)
        {
            ++cnt;
            if (cnt <= 1000)
               pr[++t] = i;
        }
    }
}

void read ()
{
    fin>>a+1>>b+1;
}

void print ()
{
    fout<<cnt<<"\n";

    for (int i=1; i<=t; ++i)
      fout<<pr[i]-1<<" ";
}

int main()
{
    read ();
    calc_z ();
    solve ();
    print ();
}