Cod sursa(job #2988020)

Utilizator AswVwsACamburu Luca AswVwsA Data 3 martie 2023 13:11:05
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

const int NMAX = 2000000;

int z[2 * NMAX + 1];
vector <int> sol;
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    int i;
    string a, b;
    cin >> a >> b;

    string s = a + b;
    int l, r;
    l = r = 0;
    z[0] = s.size();
    for (i = 1; i < s.size(); i++)
    {
        if (i > r)
        {
            for (int j = i, ind = 0; j < s.size() and s[j] == s[ind]; j++, ind++)
                z[i]++;
            if (r < i + z[i] - 1)
            {
                r = i + z[i] - 1;
                l = i;
            }
        }
        else
        {
            int beta = r - i + 1;
            int alfa = r - l + 1;
            int i_prim = alfa - beta;
            if (z[i_prim] != beta)
                z[i] = min(z[i_prim], beta);
            else
            {
                for (int j = i, ind = 0; j < s.size() and s[j] == s[ind]; j++, ind++)
                    z[i]++;
                if (r < i + z[i] - 1)
                {
                    r = i + z[i] - 1;
                    l = i;
                }
            }
        }
    }
    for (i = a.size(); i < s.size(); i++)
        if (z[i] >= a.size())
        {
            sol.push_back(i - a.size());
        }
    cout << sol.size() << "\n";
    int v = min((int)sol.size(), 1000);
    for (i = 0; i < v; i++)
        cout << sol[i] << " ";
}