Cod sursa(job #2810093)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 28 noiembrie 2021 14:26:52
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;
string A,B;
vector <int> poz;
int pi[2000001],pr=0;
static void prefixe(){
int n=A.size(),q=0;
pi[1]=0;
for(int i=2;i<n;++i){
    while(q && A[q+1]!=A[i])
        q=pi[q];
    if(A[q+1]==A[i])
        ++q;
    pi[i]=q;
}
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>A>>B;
    A.insert(A.begin(),' ');
    B.insert(B.begin(),' ');
    prefixe();
    int q=1,m=B.size()-1;
    for(int i=1;i<=m;++i){
        while(q && A[q+1]!=B[i])
              q=pi[q];
         if(A[q+1]==B[i])
            ++q;
         if(q==A.size()-1){
            q=pi[A.size()-1];
            if(poz.size()<1000)
            poz.push_back(i-A.size()+1);
          pr++;
         }
    }
    cout<<pr<<"\n";
    for(auto e:poz)
        cout<<e<<" ";
}