Cod sursa(job #2402674)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 10 aprilie 2019 21:49:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
///Z

#include <fstream>
#include <algorithm>
#include <vector>

const int NMAX=4000000;

using namespace std;

int z[NMAX+5];
vector <int> v;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int main()
{
    string a,b,s;
    cin>>a>>b;
    s=a;
    s+="#";
    s+=b;
    int r=0,pozr=0;
    for(int i=1; i<(int)s.size(); ++i)
    {
        if(i>r)
        {
            while(i+z[i]<(int)s.size() && s[i+z[i]]==s[z[i]])
                z[i]++;
        }
        else
        {
            int leftover=min(z[i-pozr],r-i);
            z[i]=leftover;
            while(i+z[i]<(int)s.size() && s[i+z[i]]==s[z[i]])
                z[i]++;
        }
        if(i+z[i]>r)
        {
            r=i+z[i];
            pozr=i;
        }
    }
    int cnt=0;
    for(int i=1; i<(int)s.size(); ++i)
    {
        if(z[i]==(int)a.size())
        {
            cnt++;
            if(cnt<=1000)
                v.push_back(i-a.size()-1);
        }
    }
    cout<<cnt<<'\n';
    for( auto x: v)
        cout<<x<<" ";
    return 0;
}