Cod sursa(job #2970927)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 26 ianuarie 2023 10:02:50
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
using namespace std;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
ll i,j,k,l,s[2000001],t;string p,q;vector<int>e;
int main()
{
in>>p>>q;
for(i=1;i<p.size();i++)
{
    if(p[i]==p[j])
        ++j;
    else
    {
        do{
        j=s[j];
        }while(j&&p[i]!=p[j]);
        if(p[i]==p[j])
            ++j;
    }
    s[i]=j;
    //cout<<s[i]<<' ';
}
j=0;
for(i=0;i<q.size();i++)
{
    if(q[i]==p[j])
        ++j;
        else{
            do{
        j=s[j];
        }while(j&&p[i]!=p[j]);
        if(q[i]==p[j])
            ++j;
        }
    if(j==p.size())
    {
        if(++t<1001)
            e.push_back(i-j+1);
        j=s[p.size()-1];
    }
}
cout<<e.size()<<'\n';
for(i=0;i<bmin(e.size(),1000);i++)
    cout<<e[i]<<' ';
}