Cod sursa(job #2977199)

Utilizator DavidbosDavid David Davidbos Data 11 februarie 2023 08:55:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int pi[2000001],v[2000001];
char a[4000002],b;
int main()
{
    int n,aux,i,maxx=0,nr=0,x;
    cin>>a;
    n=strlen(a);
    a[n]='#';
    aux=n;
    while(cin>>b){
        n++;
        a[n]=b;
    }
    for(i=1;i<=n;i++){
        x=pi[i-1];
        while(x>0){
            if(a[x]==a[i]){
                pi[i]=x+1;
                x=-1;
            }
            else
                x=pi[x - 1];
        }
        if(x==0){
            if(a[0]==a[i] && i!=0)
                pi[i]=1;
            else
                pi[i]=0;
        }
        if(i>aux)
            if(aux==pi[i]){
                nr++;
                v[nr]=i;
            }
    }
    cout<<nr<<'\n';
    for(i=1;i<=nr;i++)
        cout<<v[i]-aux-aux<<" ";
    return 0;
}