Cod sursa(job #2397027)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 4 aprilie 2019 09:00:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 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 Pattern()
{
    int last = 0;
    lps[0] = 0;

    for(int i = 1; i < P.size(); ++i)
        if(P[i] == P[last])
        {
            last++;
            lps[i] = last;
        }
        else
        {
            if( last )
            {
                last = lps[last - 1];
                i--;
            }
        }

    //for(int i = 0; i < P.size(); ++i) fout << lps[i] << ' ';
}

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

    Pattern();
    int j = 0, i = 0;
    while(i < T.size())
    {
        if(T[i] == P[j])
            {
                i++;j++;
            }

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

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

    for(int i = 0; i < Pos.size() && i < 1000; ++i)
        fout << Pos[i] << ' ';
}
int main()
{
    Do();
    return 0;
}