Cod sursa(job #3290914)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 1 aprilie 2025 20:44:55
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#ifndef LOCAL
    #pragma GCC optimize("O3")
    // #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

string A, B;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> A >> B;
}
///-------------------------------------
vector<int> KMP(string s) {
    const int n = s.size();
    vector<int> kmp(n, 0);
    kmp[0] = 0; // tragem muchie (-1, 0)
    kmp[1] = (s[0] == s[1] ? 1 : 0); // 1 daca s[0] == s[1], 0 altfel
    // in funcite de caz, tragem muchie (-1, 1) sau (0, 1)

    for(int i = 2; i < n; i++) {
        int se_trage_din = kmp[i - 1];
        while(se_trage_din > 0 && s[se_trage_din] != s[i]) {
            se_trage_din = kmp[se_trage_din - 1];
        }

        if(s[se_trage_din] == s[i]) {
            kmp[i] = se_trage_din + 1;
        } else {
            kmp[i] = 0;
        }
    }

    // verificare

    for(int i = 1; i < n; i++) {
        auto prefix = s.substr(0, kmp[i]);
        auto sufix_aici = s.substr(i - kmp[i] + 1, kmp[i]);
        if(prefix != sufix_aici) {
            cerr << "kmp[" << i << "] = " << kmp[i] << endl;
            cerr << prefix << " != " << sufix_aici << endl;
        }
        assert(prefix == sufix_aici);
    }

    return kmp;
}
///-------------------------------------
inline vector<int> get_aparitii(vector <int> &kmp)
{
    vector <int> aparitii;
    for (int i = 0 ; i < kmp.size() ; ++ i)
    {
        if (kmp[i] == A.length())
        {
            aparitii.push_back((i - (A.length() + 1)) - A.length() + 1);
        }
    }

    return aparitii;
}
///-------------------------------------
inline void Solution()
{
    auto kmp = KMP(A + "#" + B);
    auto aparitii = get_aparitii(kmp);

    cout << aparitii.size() << "\n";
    for (int i = 0 ; i < min(int(aparitii.size()), 1000) ; ++ i) cout << aparitii[i] << " ";
}
///-------------------------------------
inline void Output()
{

}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}