Cod sursa(job #2729402)

Utilizator rapidu36Victor Manz rapidu36 Data 24 martie 2021 18:03:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 2 + 2e6;
const int NMAX = 1e3;

char a[N], b[N];
int pred[N];
vector<int> poz;

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in >> (1 + a) >> (1 + b);
    in.close();
    int m = strlen(1 + a), n = strlen(1 + b);
    int lung = 0;
    for (int i = 2; i <= m; i++)
    {
        while (lung > 0 && a[i] != a[lung + 1])
        {
            lung = pred[lung];
        }
        if (a[i] == a[lung + 1])
        {
            lung++;
        }
        pred[i] = lung;
    }
    lung  = 0;
    for (int  j = 1; j <= n; j++)
    {
        while (lung > 0 && b[j] != a[lung + 1])
        {
            lung = pred[lung];
        }
        if (b[j] == a[lung + 1])
        {
            lung++;
        }
        if (lung == m)
        {
            poz.push_back(j - m);
        }
    }
    out << poz.size() << "\n";
    if (poz.size() > NMAX)
    {
        poz.erase(poz.begin() + NMAX, poz.end());
    }
    for (auto p: poz)
    {
        out << p << " ";
    }
    out.close();
    return 0;
}