Cod sursa(job #2396340)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 3 aprilie 2019 13:47:33
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int NMAX = 2000001;

string P, T;

vector <int> Pos;
int lps[NMAX];

void Precalc()
{
    for(int i = 1; i < P.size(); ++i)
        if(P[lps[i-1]] == P[i])lps[i] = lps[i-1] + 1;

}

void Read()
{
    fin >> P >> T;

    Precalc();

    int i, j;
    i = j = 0;

    for(int i = 0; i < T.size(); ++i)
    {
        if(T[i] == P[j])
        {
            if(j == P.size() - 1)
            {
                Pos.push_back(i);
                j = lps[j-1];
            }
            j++;
        }
        else j = lps[j-1];
    }

    fout << Pos.size() << '\n';

    for(int i = 0; i < Pos.size(); ++i)
        fout << Pos[i] - P.size() + 1<< ' ';
}
int main()
{
    Read();
    return 0;
}