Cod sursa(job #3295153)

Utilizator andrei.nNemtisor Andrei andrei.n Data 2 mai 2025 19:28:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

string a,b;
string v;
int pi[4000005];

signed main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    fin>>a>>b;
    v = ' ' + a + "#" + b;
    int n = v.size() - 1;
    vector<int> res;
    int cnt = 0;
    for(int i=2; i<=n; ++i)
    {
        int val = pi[i-1];
        while(val >= 0)
        {
            if(v[i] == v[val+1])
            {
                pi[i] = val + 1;
                break;
            }
            if(val == 0) break;
            val = pi[val];
        }
        if(pi[i] >= a.size())
            if((++cnt) <= 1000)
                res.push_back(i - a.size() - a.size() - 1);
    }
    fout<<cnt<<'\n';
    for(auto &i : res) fout<<i<<' ';
    return 0;
}