Cod sursa(job #2760220)

Utilizator VladTZYVlad Tiganila VladTZY Data 24 iunie 2021 00:53:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <iostream>
#include <vector>

#define NMAX 2000005

using namespace std;

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

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

void getLps(string str, int lps[]) {
    int length = 0;
    int i = 1;

    lps[0] = 0;

    while (i < str.size()) {

        if (str[i] == str[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {

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

void getKMP(string str, string pattern, int lps[]) {
    int i = 0;
    int j = 0;

    while (i < str.size()) {

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

        if (j == pattern.size()) {
            answer.push_back(i - j);
            j = lps[j - 1];

            if (answer.size() == 1000)
                return ;
        } else {

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

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

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

    getLps(pattern, lps);
    getKMP(str, pattern, lps);

    g << answer.size() << "\n";
    for (auto a : answer)
        g << a << " ";
    g << "\n";
}