Cod sursa(job #2720870)

Utilizator GeoDinBacauTofan George GeoDinBacau Data 11 martie 2021 12:56:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("date.txt");
ofstream fcout("strmatch.out");
char pat[2000001],M[2000001];
int sol[1000],prefix[2000001],nr,n,m;

void afis(char x[])
{
    cout<<endl;
    for(int i=0;i<strlen(x);i++)
        fcout<<i<<' ';
    cout<<endl;
    for(int i=0;i<strlen(x);i++)
        cout<<x[i]<<' ';
    cout<<endl;
}

void solve()
{
    int j=0;
    for(int i=0;i<m;){
        if(M[i]==pat[j]){
            if(j==n-1){
                nr++;
                sol[nr]=i-n+1;
                j=prefix[j-1];
            }
            else{
                i++;
                j++;
            }
        }
        else if(j>0){
            j=prefix[j-1];
        }
        else{
            i++;
        }
    }
}

void construire()
{
    int j=0,i=1;
    prefix[0]=0;
    for(i=1;i<n;){
        if(pat[i]==pat[j]){
            prefix[i]=j+1;
            i++,j++;
        }
        else{
            if(j!=0)
                j=prefix[j-1];
            else{
                prefix[i]=0;
                i++;
            }
        }
    }
}

bool caz_special()
{
    if(m==n){
        if(strcmp(M,pat)==0)
            fcout<<1<<endl<<0<<' ';
        else
            fcout<<0;
        return 1;
    }
    if(n>m){
        fcout<<0;
        return 1;
    }
    return 0;
}

int main()
{
    fcin.getline(pat,100000);
    fcin.getline(M,100000);
    n=strlen(pat);
    m=strlen(M);

    if(caz_special())
        return 0;

    construire();

//    for(int i=0;i<n;i++)
//        cout<<prefix[i]<<' '; cout<<endl;

    solve();

    fcout<<nr<<endl;
    for(int i=1;i<=nr && i<=1000;i++)
        fcout<<sol[i]<<' ';

    return 0;
}