Cod sursa(job #3041621)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 31 martie 2023 20:27:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 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++)
#define f first
#define s second
#define mod 111181111
using namespace std;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
ll q,n,m,i,j,k,l,p[2000001],t[2000001];char a[2000001],b[2000001];
int main()
{
//ios_base::sync_with_stdio(false);
//in.tie(nullptr),out.tie(nullptr);
in>>a>>b;
n=strlen(a),m=strlen(b);
for(i=1;i<n;i++)
{
    while(a[i]!=a[j]&&j)
        j=p[j-1];
    if(a[i]==a[j])
        p[i]=++j;
        else p[i]=0;
}
//for(i=0;i<n;i++)cout<<p[i]<<' ';
j=0;
for(i=0;i<m;i++)
{
    while(b[i]!=a[j]&&j)
        j=p[j-1];
    if(b[i]==a[j])
        ++j;
    if(j==n)
    {
        t[k++]=i-n+1;
        j=p[j-1];
    }
}
out<<k<<'\n';
bminify(k,1000);
for(i=0;i<k;i++)out<<t[i]<<' ';
}