Cod sursa(job #2979686)

Utilizator DooMeDCristian Alexutan DooMeD Data 15 februarie 2023 18:58:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 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;
    }
    vector<int> ans;
    for(int i=temp; i<(int)n.size(); i++) 
        if(pi[i] == temp - 1) 
            ans.emplace_back(i - 2 * temp + 2);
    g << ans.size() << "\n";
    for(auto i : ans) g << i << " ";
    return 0;
}