Cod sursa(job #2979318)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 14 februarie 2023 21:55:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

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

char a[2000005], b[2000005];
int p[2000005], g[2000005] , r;

void Prefix()
{
    int n = strlen(b+1);
    int k = 0;
    p[1] = 0;
    for(int i = 2 ; i <= n ; ++i)
    {
        while(k > 0 && b[k + 1] != b[i])
            k = p[k];
        if(b[k + 1] == b[i])
            k++;
        p[i] = k;
    }
}

int main()
{
    fin >> (b + 1) >> (a + 1);
    Prefix();
    int n = strlen(a+1), m = strlen(b + 1) , k = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        while(k > 0 && b[k + 1] != a[i])
            k = p[k];
        if(a[i] == b[k + 1])
            k++;
        if(k == m && r < 1000) g[++r] = i - m;
    }
    fout << r << endl;
    for(int i = 1 ; i <= min(r , 1000) ; ++i) fout << g[i] <<" ";
}