Cod sursa(job #3151739)

Utilizator AswVwsACamburu Luca AswVwsA Data 22 septembrie 2023 18:22:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
#include <stack>
#include <cmath>
#include <queue>
#define ll long long

using namespace std;


const int NMAX = 2e6;

int z[2 * NMAX + 1];

string s;

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

vector <int> sol;
signed main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int i;
    string a;
    cin >> a;
    cin >> s;
    s = a + s;
    zfunction();
    for (i = a.size(); i < s.size() and sol.size() <= 1000; i++)
        if (z[i] >= a.size())
        {
            sol.push_back(i - a.size());
        }
    cout << sol.size() << "\n";
    for (int x : sol)
        cout << x << " ";

}