Cod sursa(job #2716494)

Utilizator rapidu36Victor Manz rapidu36 Data 5 martie 2021 11:44:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>
#include <bitset>

using namespace std;

const int N = 2000002;
const int P = 1000;

char a[N], b[N];
int pi[N];
bitset <N> c;

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in >> (1 + a) >> (1 + b);
    in.close();
    int lung = 0, m = strlen(1 + a), n = strlen(1 + b);
    pi[1] = 0;
    for (int i = 2; i <= m; i++)
    {
        while (lung > 0 && a[i] != a[lung + 1])
        {
            lung = pi[lung];
        }
        if (a[i] == a[lung + 1])
        {
            lung++;
        }
        pi[i] = lung;
    }
    lung = 0;
    int nr = 0;
    for (int i = 1; i <= n; i++)
    {
        while (lung > 0 && b[i] != a[lung + 1])
        {
            lung = pi[lung];
        }
        if (b[i] == a[lung + 1])
        {
            lung++;
        }
        if (lung == m)
        {
            //cout << i - m  + 1 << " ";
            c[i - m] = 1;
            nr++;
        }
    }
    out << nr << "\n";
    nr = P;
    for (int i = 0; i < n && nr > 0; i++)
    {
        if (c[i])
        {
            out << i << " ";
            nr--;
        }
    }
    out.close();
    return 0;
}