Cod sursa(job #2732795)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 29 martie 2021 13:05:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 200005;
char a[2*NMAX],b[NMAX];
int z[2*NMAX],rasp[2*NMAX];
int main()
{
    fin >> (a+1);
    fin >> (b+1);
    int n=strlen(a+1),m=strlen(b+1);
    int aux=n;
    a[n+1]='$';
    for(int i=n+2;i<=n+m+1;i++) a[i]=b[i-n-1];
    n=n+m+1;
    int L=0,R=0;
    for(int i=2;i<=n;i++){
        if(i<=R) z[i]=min(z[i-L+1],R-i+1);
        while(i+z[i]<=n and a[i+z[i]]==a[1+z[i]]) z[i]++;
        if(i+z[i]-1>R){
            R=i+z[i]-1;
            L=i;
        }
    }
    int dim=0;
    for(int i=aux+2;i<=n;i++){
        if(z[i]==aux){
            rasp[++dim]=i-aux-2;
        }
    }
    fout << dim << '\n';
    for(int i=1;i<=dim and i<=1000;i++)
        fout << rasp[i] << ' ';
    return 0;
}