Cod sursa(job #2918103)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 9 august 2022 20:30:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_OUT = 1000;
int out;
queue <int> sol;

const int LIM = 2000005;
int n, m, len, kmp[LIM];
string pattern, text;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>pattern>>text;
    pattern = " " + pattern, n = (int)pattern.size() - 1;
    text = " " + text, m = (int)text.size() - 1;

    kmp[1] = len = 0;
    for(int i=2; i<=n; i++){
        while(len > 0 && pattern[len+1] != pattern[i])
            len = kmp[len];

        if(pattern[len+1] == pattern[i])
            len++;

        kmp[i] = len;
    }

    len = 0;
    for(int i=1; i<=m; i++){
        while(len > 0 && pattern[len+1] != text[i])
            len = kmp[len];

        if(pattern[len+1] == text[i])
            len++;

        if(len == n){
            out++;
            if(out <= MAX_OUT)
                sol.push(i - len);
        }
    }

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