Cod sursa(job #3308540)

Utilizator aaagabiTurbinca Gabriel aaagabi Data 25 august 2025 22:08:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

//#pragma GCC target("avx2")
#define int long long
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//using namespace __gnu_pbds;
using namespace std;
//ofstream fout("date.out");
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//template <class T>
//using Tree =
//    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
int n;
int pi[4000005];
void getpi(string s)
{
    for(int i=1;i<s.size();i++)
    {
        int j=pi[i-1];
        while(s[j]!=s[i]&&j>0)
        {
            j=pi[j-1];
        }
        if(s[i]==s[j])
            j++;
        pi[i]=j;
    }
}
string s,t;
void solve()
{
    fin>>s>>t;
    t=s+'#'+t;
    getpi(t);
    int cnt=0;
    vector <int> ans;
    for(int i=0;i<t.size();i++)
        if(pi[i]==s.size())
    {
        cnt++;
        if(cnt<=1000)
            ans.push_back(i-2*s.size());
    }
    fout<<cnt<<'\n';
    for(int i:ans)
        fout<<i<<' ';
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    //fin>>t;
    while(t--)
        solve();
    return 0;
}