Cod sursa(job #3156031)

Utilizator lolismekAlex Jerpelea lolismek Data 10 octombrie 2023 13:54:43
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define pii pair <int, int>

string filename = "dijkstra";

#ifdef LOCAL
    ifstream fin("input.in");
    ofstream fout("output.out");
#else
    ifstream fin(filename + ".in");
    ofstream fout(filename + ".out");
#endif

const int NMAX = 4e6;

int kmp[NMAX + 1];

void Kmp(string s){
    kmp[1] = 0;
    for(int i = 2; i < (int)s.size(); i++){
        int l = kmp[i - 1];
        while(l > 0 && s[i] != s[l + 1]){
            l = kmp[l];
        }

        if(s[i] == s[l + 1]){
            kmp[i] = l + 1;
        }
    }
}

int main(){

    string a, b;
    fin >> a >> b;

    int x = (int)a.size();

    a = "$" + a + "$" + b;

    Kmp(a);

    int cnt = 0;
    vector <int> ans;
    for(int i = x + 2; i < (int)a.size(); i++){
        if(kmp[i] == x){
            cnt++;
            if(ans.size() < 1000){
                ans.push_back(i - x - 2 - x + 1);
            }
        }
    }

    fout << cnt << '\n';
    for(int j : ans){
        fout << j << ' ';
    }
    fout << '\n';

    return 0;
}