Cod sursa(job #2761524)

Utilizator VladTZYVlad Tiganila VladTZY Data 2 iulie 2021 16:20:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>

#define NMAX 2000005
#define LIMIT 1000

using namespace std;

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

int lps[NMAX], fullAnswer;
string str, pat;
vector <int> answer;

void getKmp(string str, string pat) {
    int i = 0;
    int j = 0;

    while (i < str.size()) {

        if (str[i] == pat[j]) {
            i++;
            j++;
        }

        if (j == pat.size()) {
            fullAnswer++;
            if (answer.size() < LIMIT)
                answer.push_back(i - j);

            j = lps[j - 1];
        } else {

            if (i < str.size() && str[i] != pat[j]) {

                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
    }

}

void getLps(string pat) {
    int len = 0;
    int i = 1;
    lps[0] = 0;

    while (i < pat.size()) {

        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {

            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

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

    getLps(pat);
    getKmp(str, pat);

    g << fullAnswer << "\n";
    for (auto a : answer)
        g << a << " ";

    return 0;
}