Cod sursa(job #3346437)

Utilizator parrot279Sofi Tudose parrot279 Data 13 martie 2026 16:26:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2e6+2;

string a, b;
int n, m, kmp[nmax];

int main()
{
    fin>>a>>b;
    a = "%" + a;
    b = "%" + b;
    n = a.size() - 1;
    m = b.size() - 1;

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

        if(a[i] == a[l+1])
            ++l;

        kmp[i] = l;
    }

    int l = 0, cnt = 0, ans[1002];
    for(int i = 1; i <= m; ++i)
    {
        while(l > 0 && b[i] != a[l+1])
            l = kmp[l];

        if(b[i] == a[l+1])
            ++l;
        if(l == n)
        {
            ++cnt;
            if(cnt <= 1000)
                ans[cnt] = i-l;
        }
    }
    fout<<cnt<<"\n";
    cnt = min(1000, cnt);
    for(int i = 1; i <= cnt; ++i)
        fout<<ans[i]<<" ";

    return 0;
}