Cod sursa(job #3334927)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 20 ianuarie 2026 18:02:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[2000009], t[2000009];
vector <int> ans;
int lps[2000009];
signed main ()
{
    f.getline (s+1, 2000001);
    f.getline (t+1, 2000001);
    int l1=strlen (s+1), l2=strlen (t+1);
    int x=0;
    for (int i=2; i<=l1; i++)
    {
        x=lps[i-1];
        while (x && s[x+1]!=s[i])
            x=lps[x];
        if (s[x+1]==s[i])
        {
            x++;
            lps[i]=x;
        }
    }
    x=0;
    for (int i=1; i<=l2; i++)
    {
        while (x>0 && s[x+1]!=t[i])
            x=lps[x];
        if (s[x+1]==t[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] << ' ';
}