Cod sursa(job #2984764)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 24 februarie 2023 20:51:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
const int nmx = 2e6 + 4;
string pat,b;
int pi[nmx];
#if 1
#define cin fin
#define cout fout
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#endif
void calcPi(){
    for(int i=1;i<pat.size();i++){
        int j = pi[i-1];
        while(j>0 && pat[i]!=pat[j])
            j = pi[j-1];
        if(pat[i] == pat[j])
            j++;
        pi[i] = j;
    }
}

int main(){
    cin >> pat >> b;
    calcPi();
    int j=0;
    vector<int> m;
    for(int i=0;i<b.size();i++){
        while(j>0 && pat[j]!=b[i])
            j = pi[j-1];
        if(pat[j]==b[i])
            j++;
        if(j == pat.size()){
            m.push_back(i-pat.size()+1);
            if(m.size()==1000)
                break;
        }
    }
    cout << m.size() << "\n";
    for(int to : m)
        cout << to << " ";
}