Cod sursa(job #3246774)

Utilizator victorzarzuZarzu Victor victorzarzu Data 4 octombrie 2024 14:56:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

string a, b;
int pq[2000005], nr;
vector<int> result;

void read() {
    f>>a;
    f>>b;
    a.insert(0, " ");
    b.insert(0, " ");
    
    f.close();
}

void precompute() {
    int q = 0;
    for(int i = 2;i < a.size();++i)  {
        while(q && a[q + 1] != a[i]) {
            q = pq[q];
        }
        if(a[q + 1] == a[i]) {
            q++;
        }
        pq[i] = q;
    }
}

void solve() { 
    int q = 0;
    for(int i = 1;i < b.size();++i) {
        while(q && a[q + 1] != b[i]) {
            q = pq[q];
        }

        if(a[q + 1] == b[i]) {
            q++;
        }

        if(q == a.size() - 1) {
            nr++;
            if(nr <= 1000) {
                result.push_back(i - q);
            }
            q = pq[q];
        }
    }
}

void print() {
    g<<nr<<'\n';
    for(const auto& poz : result) {
        g<<poz<<" ";
    }
    g.close();
}

int main() {
    read();
    precompute();
    solve();
    print();



    return 0;
}