Cod sursa(job #2717742)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 7 martie 2021 21:12:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2e6;
int lpp[NMAX + 5], n, len;
string pat, str;
void precalc_lpp() {
    pat = " " + pat + " "; str = " " + str;
    lpp[1] = 0;
    int k = 0; len = pat.length() - 2; n = str.length() - 1;
    for(int i = 2; i <= len; i++) {
        while(k > 0 && pat[k + 1] != pat[i])
            k = lpp[k];
        if(pat[k + 1] == pat[i]) k++;
        lpp[i] = k;
    }
}

int main()
{
    fin >> pat >> str;
    precalc_lpp();
    //for(int i = 1; i <= len; i++) fout << lpp[i] << " "; fout << "\n";
    int k = 0, res = 0;
    vector <int> sol;
    for(int i = 1; i <= n; i++) {
        while(k > 0 && pat[k + 1] != str[i])
            k = lpp[k];
        if(pat[k + 1] == str[i]) k++;
        if(k == len) {
            if(res < 1000) sol.push_back(i - len + 1);
            res++;
        }
    }
    fout << res << "\n";
    for(auto el : sol) fout << el - 1 << " ";
    return 0;
}