Cod sursa(job #2770293)

Utilizator IacobTudorIacob Tudor IacobTudor Data 20 august 2021 13:27:10
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
/**
 ____ ____ ____ ____ ____
||O |||M |||E |||G |||A ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|


Se spune ca sunt vise
Si ca nu pot fi atinse
Sunt primele ce le vezi cand becurile-s stinse
Dar si cand is aprinse
Cand te trezesti cu ele-n gand
Si le vizualizezi din nou rand pe rand
Se spune ca visezi daca stai si-ti imaginezi
Ca esti altfel decat ceilalti, dar nu tre sa crezi
Continua sa lupti altfel imi vei da dreptate
Vei bea pe spate cu gandul la vise spulberate
    - "Vise" - Nane -

Тяжело стать богатым, но тяжелее остаться.

**/
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
int x[2000005],v[2000005],k;
int main(){
    fin>>(a+1)>>(b+1);
    int n(strlen(a+1)),m(strlen(b+1));
    int p(1);
    for(int i=2;i<=n;i++){
        while(p>1&&a[i]!=a[p])p=x[p-1];
        if(a[i]==a[p])p++;
        x[i]=p;
    }
    p=1;
    for(int i=1;i<=m;i++){
        while(b[i]!=a[p]&&p>1)p=x[p-1];
        if(b[i]==a[p]){
            p++;
            if(p>n){
                v[++k]=i-n;
                p=x[n];
            }
        }
    }
    fout<<k<<"\n";
    for(int i=1;i<=k;i++)fout<<v[i]<<" ";
    return 0;
}