Cod sursa(job #3329844)

Utilizator TzepuAndrei Tzepu Data 16 decembrie 2025 10:52:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

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

int inc[2000001],f[2000001];

int main()
{
    string s1, s2;
    in >> s1 >> s2;
    string s = s1 + "#" + s2;
    int kmp[s.size()+1]={0};
    kmp[1] = 0;
    for (int i=2; i<=s.size(); i++) {
        int l=kmp[i-1];
        while (l>0 && s[l]!=s[i-1]) {
            l=kmp[l];
        }
        if (s[l] == s[i - 1]) {
            kmp[i] = l + 1;
        }
    }
    int v[100001];
    int cnt=0;
    for (int i=1; i<=s.size(); i++) {
        if (kmp[i]==s1.size()) {
            v[++cnt]=i-2*s1.size()-1;
        }
    }
    out << cnt << "\n";
    for (int i=1; i <=cnt; i++) {
        out << v[i] << " ";
    }
    return 0;
}