Cod sursa(job #3343703)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 28 februarie 2026 11:24:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <cstring>
#define nmax (int)(2e6+1)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int lps[nmax],n,m,sol;
string s,a;
vector<int>poz;
void get_lps(){
    int i=1,len=0;
    while(i<n){
        if(s[i]==s[len])
            lps[i++]=++len;
        else if(len==0)
            i++;
        else
            len=lps[len-1];
    }
}
void solve(){
    int i=0,j=0;
    while(j<m){
        if(s[i]==a[j])
            i++,j++;
        else if(i!=0)
            i=lps[i-1];
        else
            j++;
        if(i==n){
            sol++;
            if(sol<=1000)
                poz.push_back(j-n);
            i=lps[n-1];
        }
    }
}
signed main()
{
    cin>>s>>a;
    n=s.size();
    m=a.size();
    get_lps();
    solve();
    cout<<sol<<'\n';
    for(auto i:poz)
        cout<<i<<" ";
    return 0;
}