Cod sursa(job #2720996)

Utilizator GeoDinBacauTofan George GeoDinBacau Data 11 martie 2021 14:41:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("strmatch.in");
ofstream fcout("strmatch.out");
char pat[2000003],M[2000003];
int sol[1069],prefix[2000003],nr,n,m;



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;
}

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

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

//    if(caz_special())
//        return 0;

    construire();

    solve();

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

    return 0;
}