Cod sursa(job #3180250)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 4 decembrie 2023 21:25:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
#define NMAX 1000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[NMAX];
char p[NMAX];
int pi[NMAX];
vector <int> sol;
void gen_prefix(){
    int n = strlen(p), k = 0;
    pi[0] = 0;
    for(int i = 1; i < n; i++){
        while(k > 0 && p[i] != p[k]) k = pi[k - 1];
        if(p[k] == p[i]) k++;
        pi[i] = k;
    }
}
void kmp(){
    int n = strlen(s), m = strlen(p),k = 0;
    for(int i = 0; i < n; i++){
        while(k > 0 && p[k] != s[i]) k = pi[k - 1];
        if(p[k] == s[i]) k++;
        if(k == m) sol.push_back(i - m + 1);
    }
}
int main()
{
    fin >> p;
    fin.get();
    fin >> s;
    gen_prefix();
    kmp();
    fout << sol.size() << "\n";
    for(auto x : sol) fout << x << " ";
    return 0;
}