Cod sursa(job #2402672)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 10 aprilie 2019 21:48:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>

const int NMAX=4000000;

using namespace std;

int k[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;
    for(int i=2; i<(int)s.size(); ++i)
    {
        int q=k[i-1];
        while(q && s[i]!=s[q+1])
            q=k[q];
        if(s[q+1]==s[i])
            ++q;
        k[i]=q;
    }
    int cnt=0;
    for(int i=1; i<(int)s.size(); ++i)
    {
        if(k[i]==(int)a.size())
        {
            cnt++;
            if(cnt<=1000)
                v.push_back(i-2*a.size()-1);
        }
    }
    cout<<cnt<<'\n';
    for( auto x: v)
        cout<<x<<" ";
    return 0;
}