Cod sursa(job #2771418)

Utilizator OvidRata Ovidiu Ovid Data 27 august 2021 11:33:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 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


int t, n, m, k, a[300010], q, l, r;



void kmp(int pi[], string &s  ){
pi[0]=0;

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

return;
}


int pi[4000005];

pair<int, vector<int>> match(string &t, string &p ){

string s=p+"#"+t;
//cout<<s<<"\n";
//cout<<"ok\n"<<flush;
kmp(pi, s);
//cout<<"ok\n"<<flush;
int lp=p.length();
vector<int> res;
int cnt=0;
for(int i=lp+1; i<s.length(); i++){
    if( (pi[i]==lp) ){
        cnt++;
        if(res.size()<1000){res.pb(i-(lp+1)-(lp-1) );}
    //    cnt++;
    }


}

return {cnt, res};
}





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


int32_t main(){
INIT



    string a, b;
    cin>>b>>a;
    pair<int, vector<int>> rs=match(a, b);
    vector<int> res=rs.sc; int cnt=rs.ft;

        cout<<cnt<<"\n";
        for(int &x:res){
            cout<<x<<" ";
        }
        //cout<<"\n\n";


return 0;
}