Cod sursa(job #3241820)

Utilizator CondoracheAlexandruCondorache Alexandru CondoracheAlexandru Data 4 septembrie 2024 15:46:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
using namespace std;
const int maxn=1e5+5;

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

vector<int> prefix_funciton(string s) {
    int n = (int)s.length();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}


void solve() {
    string t;
    string s;
    fin >> s;
    fin >> t;
    string temp = s + '#' + t;
    int sz = s.size() + t.size() + 1;
    auto pi = prefix_funciton(temp);
    int counter = 0;
    vector<int> ans;
    for (int i = 0; i < sz; i++) {
        if (pi[i] == (int)s.size()) {
            //cout << i - 2 * s.size() << " ";
            counter++;
            if (counter <= 1000)
                ans.pb(i - 2 * s.size());
        }
    }
    fout << counter << endl;
    for (auto v : ans) {
        fout << v << " ";
    }
    return;
}

int main() {
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}