Cod sursa(job #2919820)

Utilizator OvidRata Ovidiu Ovid Data 19 august 2022 21:04:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll

ifstream fin("strmatch.in"); ofstream fout("strmatch.out");
#define cin fin
#define cout fout



int n, m;
string a, b;


int pi[4000001];

void buildPi(string s, int pi[]){

for(int i=1, j=0; i<s.length(); i++){
    while( (j>0) && (s[j]!=s[i])  ){
        j=pi[j-1];
    }
    if(s[j]==s[i]){
        pi[i]=++j;
    }
}

}


int cnt;
vector<int> res;

void match(int n, int sz, int pi[]){

for(int i=0; i<sz; i++){
    if(pi[i]==n){
        cnt++;
        if(res.size()<1000){
            res.pb(i-(n+1)-n+1);
        }
    }
}

}

int32_t main(){
INIT
cin>>a>>b;
int n=a.length(), m=b.length();
buildPi(a+"$"+b, pi);
match(n, n+m+1, pi);

cout<<cnt<<"\n";
for(int i=0; i<res.size(); i++){
    cout<<res[i]<<" ";
}


return 0;
}