Cod sursa(job #2298395)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 8 decembrie 2018 09:40:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int LGMax = 2000005;

char x[2 * LGMax+5];
char y[LGMax+5];

int n, m, nr;

int phi[2 * LGMax + 5];

vector <int> Sol;

void Construire_Phi ()
{
    strcat(x, "#");
    strcat(x, y);

    n = strlen(x);

    int rez = 0;

    for (int i = 1; i < n; i++)
    {
        while (rez > 0 && x[i] != x[rez])
        {
            rez = phi[rez-1];
        }

        if (x[rez] == x[i]) rez++;

        phi[i] = rez;
    }
}

void solve ()
{
    Construire_Phi();

    for (int i = m + 1; i < n; i++)
    {
        if (phi[i] == m) {
            nr++;
            Sol.push_back(i - m - 1);
        }
    }

    g << nr << '\n';

    for (int i = 0; i < 1000 && i < Sol.size(); i++)
    {
        g << Sol[i] - m + 1 << " ";
    }
}
int main()
{
    f.getline(x, LGMax);
    f.getline(y, LGMax);

    m = strlen(x);

    solve();
    return 0;
}