Cod sursa(job #3209875)

Utilizator Alex_Mihai10Mihai Alex-Ioan Alex_Mihai10 Data 3 martie 2024 18:00:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define MAX 2000005

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char sirA[MAX],sirB[MAX];
int lpsA[MAX],raspB[MAX];
int ind[1005];

int main()
{
    fin.getline(sirA,MAX);
    fin.getline(sirB,MAX);

    int i;
    for(i=1;sirA[i];++i)
    {
        int lg=lpsA[i-1];
        while(lg && sirA[lg]!=sirA[i])
            lg=lpsA[lg-1];
        if(sirA[lg]==sirA[i])
            lpsA[i]=lg+1;
    }

    int n=0;
    int sz=strlen(sirA);
    for(i=0;sirB[i];++i)
    {
        int lg=raspB[i-1];
        while(lg && sirA[lg]!=sirB[i])
            lg=lpsA[lg-1];
        if(sirA[lg]==sirB[i])
            raspB[i]=lg+1;
        if(raspB[i]==sz)
        {
            ++n;
            if(n<=1000)
                ind[n]=i-sz+1;
        }
    }

    fout<<n<<'\n';
    for(i=1;i<=min(n,1000);++i)
        fout<<ind[i]<<' ';

    return 0;
}