Cod sursa(job #3348102)

Utilizator stefan_ciureaStefan Ciurea stefan_ciurea Data 19 martie 2026 17:45:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax=2e6+5;

int n,pi[Nmax];

void kmp(string s) {
    int k=0;
    for (int i=1; i<n; ++i) {
        while (k && s[k]!=s[i]) k=pi[k-1];
        if (s[k]==s[i]) k++;
        pi[i]=k;
    }
}

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a,b;
    cin>>a>>b;
    n=a.size();
    int m=b.size();
    kmp(a);
    vector<int> ans;
    int k=0,lim=1000;
    for (int i=0; i<m; ++i) {
        while (k && a[k]!=b[i]) k=pi[k-1];
        if (a[k]==b[i]) k++;
        if (k==n) {
            ans.push_back(i-n+1);
            k=pi[k-1];
        }
    }
    cout<<ans.size()<<'\n';
    for (int i=0; i<min((int)ans.size(),lim); ++i) cout<<ans[i]<<' ';
    cin.close();
    cout.close();
    return 0;
}