Cod sursa(job #2722477)

Utilizator danhHarangus Dan danh Data 12 martie 2021 21:18:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

string a, b;

const int NMAX = 2000005;

int pi[NMAX];

void computePi(string x)
{
    int len = 0, i = 1;
    while(i < x.size())
    {
        if(x[len] == x[i])
        {
            len++;
            pi[i] = len;
            i++;
        }
        else
        {
            if(len)
            {
                len = pi[len-1];
            }
            else
            {
                i++;
            }
        }
    }
}

vector<int> sol;

int nr;

void kmp(string text, string pat)
{
    computePi(pat);
    int i = 0, len = 0;
    while(i < text.size())
    {
        if(text[i] == pat[len])
        {
            i++;
            len++;
        }
        else
        {
            if(len)
            {
                len = pi[len-1];
            }
            else
            {
                i++;
            }
        }
        if(len == pat.size())
        {
            nr++;
            if(sol.size() < 1000)
            {
                sol.push_back(i - pat.size());
            }
            len = pi[len-1];
        }
    }
}

int main()
{
    fin>>a>>b;

    kmp(b, a);

    fout<<nr<<'\n';
    for(int el : sol)
    {
        fout<<el<<' ';
    }

    fin.close();
    fout.close();
    return 0;
}