Cod sursa(job #3348965)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 24 martie 2026 20:40:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000009], s2[2000009];
int lps[2000009];
signed main ()
{
    f.getline (s1+1, 2000001);
    f.getline (s2+1, 2000001);
    int x=0;
    int l1=strlen(s1+1);
    int l2=strlen(s2+1);
    for (int i=2; i<=l1; i++)
    {
        x=lps[i-1];
        while (x && s1[x+1]!=s1[i])
            x=lps[x];
        if (s1[x+1]==s1[i])
            lps[i]=x+1;
    }
    vector <int> ans;
    x=0;
    for (int i=1; i<=l2; i++)
    {
        while (x && s1[x+1]!=s2[i])
            x=lps[x];
        if (s1[x+1]==s2[i])
            x++;
        if (x==l1)
            ans.push_back(i-l1);
    }
    g << ans.size()<<'\n';
    for (int i=0; i<min (int(ans.size()), 1000); i++)
        g <<ans[i]<< ' ';
}