Cod sursa(job #3290917)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 1 aprilie 2025 20:47:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include<bits/stdc++.h>
 
using namespace std;
 
const int NMAX = 2e6 + 5;
 
int kmp[NMAX];
string a, b;
vector<int> ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
 
    cin >> a >> b;
 
    if(a.size() > b.size())
    {
        cout << "0\n";
        return 0;
    }
 
    int k = 0, i = 1;
    while(i < a.size())
    {
        if(a[i] == a[k])
        {
            k++;
            kmp[i] = k;
            i++;
        }
        else 
        {
            if(k)
                k = kmp[k - 1];
            else    
                i++;
        }
    }
 
    i = 0;
    int j = 0;
    while(b.size() - j >= a.size() - i)
    {
        if(a[i] == b[j]) 
        {
            i++;
            j++;
        }
 
        if(i == a.size())
        {
            ans.push_back(j - i);
            i = kmp[i - 1];
        }
        else if(j < b.size() && b[j] != a[i])
        {
            if(i != 0)
                i = kmp[i - 1];
            else
                j++;
        }
    }
 
    int val = ans.size();
    cout << val << "\n";
    for(int i = 0; i < min(val, 1000); i++)
        cout << ans[i] << " ";
}