Cod sursa(job #3183397)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 11 decembrie 2023 19:08:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#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 1000000007ll
#define nmax 2000002
#define lim 351
using namespace std;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
//FILE *fin=fopen("infasuratoare.in","r");
//FILE *fout=fopen("infasuratoare.out","w");
int n,m,i,j=-1,k,l,p[nmax]={-1},c[nmax];char a[nmax],b[nmax];
int main()
{
in>>a>>b;
n=strlen(a),m=strlen(b);
for(i=1;i<n;i++)
{
    ++j;
    while(j>0&&a[i]!=a[j])j=p[j-1]+1;
    if(a[i]!=a[j])--j;
    p[i]=j;
    //cout<<i<<' '<<j<<'\n';
}
j=-1;
for(i=0;i<m;i++)
{
    ++j;
    while(j>0&&b[i]!=a[j])j=p[j-1]+1;
    if(b[i]!=a[j])
        --j;
        else if(j==n-1)c[l++]=i-n+1;
}
out<<l<<'\n';
forq(i,0,bmin(1000,l))out<<c[i]<<' ';
}