Cod sursa(job #3328995)

Utilizator Andrada_MincaAndrada Minca Andrada_Minca Data 11 decembrie 2025 15:26:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
//
//  main.cpp
//  Potrivirea sirurilor
//
//  Created by Andrada Minca on 11.12.2025.
//

#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector<int> lps(2000005,0),ans;
void build_lps(string a)
{
    int n=a.size(),k=0;
    for(int i=2;i<=n;i++)
    {
        while(k&&a[i-1]!=a[k])k=lps[k];
        if(a[i-1]==a[k])k++;
        lps[i]=k;
    }
}
void kmp(string a,string b)
{
    int nr=0;
    int m=b.size(),n=a.size();
    int k=0;
    for(int i=0;i<m;i++)
    {
        while(k&&a[k]!=b[i])k=lps[k];
        if(a[k]==b[i])k++;
        if(k==n)ans.push_back(i-n+1),nr++;
    }
    cout<<nr<<'\n';
    for(int i=0;i<min(1000,nr);i++)cout<<ans[i]<<" ";
}
int main()
{
    string a,b;
    cin>>a>>b;
    build_lps(a);
    kmp(a,b);
    return 0;
}