Cod sursa(job #2848543)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 12 februarie 2022 19:53:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#define boostIO ios_base::sync_with_stdio(false); fin.tie(nullptr); fout.tie(nullptr);
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define uint unsigned int

using namespace std;

ifstream fin  ("strmatch.in");
ofstream fout ("strmatch.out");

const int OUT_LIMIT = 1000;
int out_cnt;
queue <int> sol;


const int STR_SIZE = 2000000;
string txt, fnd;
int len, kmp[2 * STR_SIZE + 5];

signed main (){
    boostIO

    fin>>fnd>>txt;
    txt = " " + fnd + "#" + txt;

    kmp[0] = -1;
    for(int i=1; i < (int)txt.size(); i++){
        len = kmp[i-1];
        while(len >= 0 && txt[i] != txt[len+1])
            len = kmp[len];
        kmp[i] = len + 1;
    }

    for(int i=1; i < (int)txt.size(); i++)
        if(kmp[i] == (int)fnd.size())
            if(++out_cnt <= OUT_LIMIT)
                sol.push(i - 2*(int)fnd.size() - 1);

    fout<<out_cnt<<"\n";
    while(!sol.empty()){
        fout<<sol.front()<<" ";
        sol.pop();
    }
    return 0;
}