Cod sursa(job #2863023)

Utilizator radu.Radu Cristi radu. Data 6 martie 2022 11:26:12
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string w, s;
int N;
int T[NMAX];
void createPartialMatchTable() {
    T[0] = 0;
    int j = 0;
    for (int i = 1; i < w.length(); ++i) {
        if (w[j] == w[i]) {
            T[i] = j + 1;
            ++j;
        }
        else {
            while (w[i] != w[j] && j > 0) {
                j = T[j - 1];
            }
            if (j == 0 && w[i] != w[j]) {
                T[i] = 0;
            }
            else
                T[i] = j + 1;
        }
    }
}
vector<int> solutions;
void kmp() {
    int j = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == w[j]) {
            ++j;
            if (j == w.length()) {
                solutions.push_back(i - w.length() + 1);
                j = T[j - 1];
            }
        }
        else {
            while (s[i] != w[j] && j > 0) {
                j = T[j - 1];
            }
            if (s[i] == w[j]) {
                ++j;
            }
        }
    }
}
int main()
{
    fin >> w >> s;
    createPartialMatchTable();
    kmp();
    fout << solutions.size() << "\n";
    int N = min(solutions.size(), (size_t)1000);
    for (int i = 0; i < N; ++i) {
        fout << solutions[i] << " ";
    }
    return 0;
}