Cod sursa(job #2722814)

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

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

const int NMAX = 2e6+5;

string a, b;

vector<int> sol;

int pi[NMAX];

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

        }
        else
        {
            if(len)
            {
                len = pi[len-1];
            }
            else
            {
                i++;
            }
        }
    }
}

int nr;
void KMP(string pat, string text)
{
    computePi(pat);
    int i = 0, len = 0;
    while(i < text.size())
    {
        if(text[i] == pat[len])
        {
            len++;
            i++;
        }
        else
        {
            if(len)
            {
                len = pi[len-1];
            }
            else
            {
                i++;
            }
        }
        if(len == pat.size())
        {
            nr++;
            if(nr < 1000)
            {
                sol.push_back(i - len);
            }
            len = pi[len-1];
        }
    }
}
int main()
{
    fin>>a>>b;
    KMP(a, b);
    fout<<nr<<'\n';
    for(auto el : sol)
    {
        fout<<el<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}