Cod sursa(job #2979310)

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

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

char a[105], b[105];
int p[105], g[105] , 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] <<" ";
}