Cod sursa(job #1629593)

Utilizator AeroHHorea Stefan AeroH Data 4 martie 2016 16:39:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
string z = "strmatch.";
ifstream f(z+"in");
ofstream g(z+"out");
int i,j,la,l,r,Z[2000005*2],ans;
string a,b;
vector<int> rasp;

void expand(){while(a[r+1] == a[r-l+1] && r + 1 < a.size())++r;}
int main()
{
    f>>a>>b;
    la=a.size();
    a+=b;

    Z[0]=a.size();
    for(i=1;i<a.size();++i)
    {
        Z[i]=0;
        if (l<=i && i<=r)
        {
            if (Z[i-l]>=r-i+1)
            {
                l=i;
                expand();
                Z[i]=r-l+1;
            }
            else Z[i]=Z[i-l];
        }
        else if (a[i]==a[0])
        {
            l=r=i;
            expand();
            Z[i]=r-l+1;
        }
    }
    for (i=la;i<=a.size();++i)
        if (Z[i]>=la)
            {
                ++ans;
                if (ans<=1000)
                    {
                        rasp.push_back(i);
                    }
            }
    g<<ans<<'\n';
    for(i=0;i<rasp.size();++i)
        g<<rasp[i]-la<<" ";



    return 0;
}