Cod sursa(job #1253941)

Utilizator AeroHHorea Stefan AeroH Data 1 noiembrie 2014 23:18:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string a,b;
int i,j,la,l,r,Z[2000005*2],ans;
vector<int> rasp;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

void expand(){while(a[r+1] == a[r-l+1] && r + 1 < a.size())++r;}
int main()
{
    cin>>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;
                }
            //cout<<"I = "<<i<<" , "<<"L = "<<l<<" , "<<"R = "<<r<<" , "<<"Z[i] = "<<Z[i]<<'\n';
        }
    for (i=la;i<=a.size();++i)
        if (Z[i]>=la)
            {
                ++ans;
                if (ans<=1000)
                    {
                        rasp.push_back(i);
                    }
            }
    cout<<ans<<'\n';
    for(i=0;i<rasp.size();++i)
        cout<<rasp[i]-la<<" ";



    return 0;
}