Cod sursa(job #2563487)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 1 martie 2020 11:58:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>

using namespace std;

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

string pat, str;
int z[4000010];

void zBuild(string x)
{
    int L = 0, R = 0, k;
    int n = x.size();

    for(int i = 1; i <= n; i++)
    {
        if(i > R)
        {
            L = R = i;

            while(R <= n && x[R - L] == x[R])
                R++;

            z[i] = R - L;

            R--;
        }
        else
        {
            k = i - L;

            if(z[k] < R - i + 1)
                z[i] = z[k];

            else
            {
                L = i;

                while(R <= n && x[R - L] == x[R])
                    R++;

                z[i] = R - L;

                R--;
            }
        }
    }
}

void solve()
{
    string concat = pat + '$' + str;
    queue<int> q;
    int limit = 1000;

    zBuild(concat);

    for(int i = 0; i < concat.size() && q.size() < limit; i++)
        if(z[i] == pat.size())
            q.push(i - pat.size() - 1);

    out << q.size() << '\n';

    while(!q.empty())
    {
        out << q.front() << ' ';

        q.pop();
    }
}

int main()
{
    in >> pat >> str;

    solve();

    return 0;
}