Cod sursa(job #2979312)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 14 februarie 2023 21:51:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 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), 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 == strlen(b+1) && r <= 1000) g[++r] = i - strlen(b+1);
    }
    fout << r << endl;
    for(int i = 1 ; i <= r ; ++i) fout << g[i] <<" ";
}