Cod sursa(job #2429468)

Utilizator ALEx6430Alecs Andru ALEx6430 Data 9 iunie 2019 18:30:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

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

string A, B;
int p[2000000], N;
vector<int> poz;

void f_prefix(int &n)
{
    int k = 0;

    p[0] = 0;

    for(int i = 1; i < n; i++)
    {
        while(k && A[i] != A[k])
            k = p[k-1];

        if(A[i] == A[k])
            k++;

        p[i] = k;
    }
}

void f_potrivire(int &n, int &m)
{
    int k = 0;

    for(int i = 0; i < m; i++)
    {
        while(k && B[i] != A[k])
            k = p[k-1];

        if(B[i] == A[k])
            k++;

        if(k == n && ++N <= 1000)
            poz.push_back(i-n+1);
    }
}

int main()
{
    in >> A >> B;

    int n = A.size();
    int m = B.size();

    f_prefix(n);
    f_potrivire(n,m);

    out << N << '\n';

    for(int i = 0; i < poz.size(); i++)
        out << poz[i] << ' ';

    return 0;
}