Cod sursa(job #3180256)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 4 decembrie 2023 21:34:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define NMAX 2000005
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()
{
    int i;
    fin >> p;
    fin.get();
    fin >> s;
    gen_prefix();
    if(strlen(p) > strlen(s)){
        fout << 0;
        return 0;
    }
    kmp();
    fout << sol.size() << "\n";
    for(i = 0; i < sol.size(); i++){
        if(i >= 1000) break;
        fout << sol[i] << " ";
    }
    return 0;
}