Cod sursa(job #2770045)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 18 august 2021 23:07:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int Nmax = 2000000;
vector <int> v;
int p[Nmax + 1];
char a[Nmax + 1], b[Nmax + 1];
int cnt;

void prefix_function()
{
    int n = strlen((a + 1));
    for (int i = 2; i <= n; i++)
    {
        int j = p[i - 1];
        while (j > 0 && a[i] != a[j + 1])
        {
            j = p[j];
        }
        if (a[i] == a[j + 1])
        {
            j++;
        }
        p[i] = j;
    }
}

void match()
{
    int m = strlen((b + 1));
    int n = strlen((a + 1));
    int j = 0;
    for (int i = 1; i <= m; i++)
    {
        while (j > 0 && b[i] != a[j + 1])
        {
            j = p[j];
        }
        if (b[i] == a[j + 1])
        {
            j++;
        }
        if (j == n)
        {
            cnt++;
            if (cnt <= 1000)
            {
                v.push_back(i - n);
            }
        }
    }
}

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> (a + 1) >> (b + 1);
    prefix_function();
    match();
    fout << cnt << "\n";
    for (auto u : v)
    {
        fout << u << " ";
    }
    return 0;
}