Cod sursa(job #3321228)

Utilizator andreiaramaArama Andrei Robert andreiarama Data 8 noiembrie 2025 17:33:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

string a, b;
int z[4000001];

int main() {
    cin >> a >> b;
    string s = a + '#' + b; 
    int l = 0, r = 0;

    for (int i = 1; i < s.size(); i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    int matches = 0;
    vector<int> m;
    int pattern_len = a.size();

    for (int i = pattern_len + 1; i < s.size(); i++) {
        if (z[i] == pattern_len) {
            matches++;
            m.push_back(i - pattern_len - 1);
        }
        if(matches==1000)break;
    }

    cout << matches << '\n';
    for (int i=0;i<matches;i++) {
        cout << m[i] << ' ';
    }

    return 0;
}