Cod sursa(job #2911079)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 26 iunie 2022 18:24:36
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda 3_iulie Marime 1.15 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <algorithm>
#include <cstring>
#include <iomanip>

#define DIM 2000000
using namespace std;


//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int asize,bsize,p[DIM+5];
char a[DIM+5],b[DIM+5];

int solk=0,sol[1005];

int main(){

    f>>(a+1);
    asize = strlen(a+1);
    f>>(b+1);
    bsize = strlen(b+1);


    int l=0;
    for(int i=2;i<=asize;i++){
        if(l!=0&&a[i]!=a[l+1]){
            l = p[l];
        }
        if(a[i] == a[l+1]){
            l++;
        }
        p[i] = l;
    }

    l=0;
    for(int i=1;i<=bsize;i++){
        if(l!=0&&b[i]!=a[l+1]){
            l = p[l];
        }
        if(b[i] == a[l+1]){
            l++;
        }
        if(l == asize){
            solk++;
            if(solk<=1000){
                sol[solk]=i-l;
            }
            l = p[l];
        }
    }

    g<<solk<<'\n';
    solk = min(solk,1000);
    for(int i=1;i<=solk;i++){
        g<<sol[i]<<" ";
    }

    f.close();
    g.close();
    return 0;
}