Cod sursa(job #2979734)

Utilizator DooMeDCristian Alexutan DooMeD Data 15 februarie 2023 20:05:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e6;

int pi[2*nmax+5];

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

    string n, m; f >> n >> m;
    int temp = n.size() + 1;
    n = n + "#" + m;
    for(int i=1; i<(int)n.size(); i++) {
        int j = pi[i-1];
        while(j > 0 and n[i] != n[j]) j = pi[j-1];
        if(n[i] == n[j]) j++;
        pi[i] = j;
    }
    int nr = 0;
    vector<int> ans;
    for(int i=temp; i<(int)n.size(); i++) 
        if(pi[i] == temp - 1) {
            nr++;
            if(ans.size() < 1000) ans.emplace_back(i - 2 * temp + 2);
        }
    g << nr << "\n";
    for(auto i : ans) g << i << " ";
    return 0;
}