Cod sursa(job #3359971)

Utilizator Zeno1789Zeno Ciuca Zeno1789 Data 7 iulie 2026 10:50:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

int main() {
    string a,b;
    cin>>a>>b;
    int n=a.length();
    int m=b.length();
    vector<int> pi(n,0);
    int j=0;
    for (int i=1; i<n; ++i) {
        while (j>0 && a[i]!=a[j]) {
            j=pi[j-1];
        }
        if (a[i]==a[j]) {
            j++;
        }
        pi[i]=j;
    }
    vector<int> matches;
    j=0;
    for (int i=0; i<m; ++i) {
        while (j>0 && b[i]!=a[j]) {
            j=pi[j-1];
        }
        if (b[i]==a[j]) {
            j++;
        }
        if (j==n) {
            matches.push_back(i-n+1);
            j=pi[n-1];
        }
    }
    cout<<matches.size()<<"\n";
    int limit=matches.size();
    if (limit>1000) {
        limit=1000;
    }
    for (int i=0; i<limit; ++i) {
        cout<<matches[i]<<(i==limit-1?"":" ");
    }
    cout<<"\n";
}