Cod sursa(job #3289190)

Utilizator Victor5539Tanase Victor Victor5539 Data 25 martie 2025 23:41:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>

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

const int MAX=2e6;
int n,m,i,lps[MAX+5],len,sol[MAX+5],nr,j;
char v[MAX+10],g[MAX+10];

void buildlps()
{
    len=0; i=1;
    lps[0]=0;

    while (i<m)
    {
        if (g[i]==g[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if (len==0)
            {
                lps[i]=0;
                i++;
            }
            else
                len=lps[len-1];
        }
    }
}

int main()
{
    fin.getline(g,MAX+5);
    fin.getline(v,MAX+5);

    m=strlen(g);
    n=strlen(v);
    buildlps();

    i=0; j=0;
    while (i<n)
    {
        if (v[i]==g[j])
        {
            i++;
            j++;

            if (j==m)
            {
                sol[++nr]=i-j;
                j=lps[j-1];
            }
        }
        else
        {
            if (j!=0)
                j=lps[j-1];
            else
                i++;
        }
    }

    fout<<nr<<"\n";
    for (i=1; i<=nr; i++)
        fout<<sol[i]<<" ";
    return 0;
}