Cod sursa(job #2923480)

Utilizator PopaMihaimihai popa PopaMihai Data 14 septembrie 2022 18:46:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string pattern, s;

const int SMAX = 2e6 + 3;

int N;
int kmp[SMAX];

void KMP(string a)
{
    int k = 0;
    N = a.size() - 1;

    kmp[1] = 0;

    for(int i = 2; i <= N; ++i) {
        while(k > 0 && a[k + 1] != a[i])
            k = kmp[k];

        if(a[k + 1] == a[i])
            ++k;

        kmp[i] = k;
    }
}

int main()
{
    fin >> pattern >> s;
    KMP ("$" + pattern + "$" + s);

    int ans = 0;
    vector < int > sol;

    for(int i = pattern.size() + 2; i <= N; ++i)
        if(kmp[i] == pattern.size())
            ++ans, sol.push_back(i - kmp[i] - 1 - pattern.size());

    fout << ans << '\n';
    for(auto it: sol)
        fout << it << ' ';
    fout << '\n';

    return 0;
}