Cod sursa(job #3000424)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 12 martie 2023 14:00:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

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

const int dim = 2e6 + 5;
const int DIM = 1e3;

vector <int> v;
char str[2 * dim] , ch;
int z[2* dim] , n , m , L , R;

int main()
{
    fin >> str;
    m = strlen(str);
    strcat(str , "$");
    n = strlen(str);
    while(fin >> ch)
        str[n++] = ch;
    L = R = 0;
    for(int i = 1 ; i < n ; ++i)
        {
            if(i > R)
                {
                    L = R = i;
                    while(R < n && str[R - L] == str[R]) ++R;
                    z[i] = R - L;
                    --R;
                }
            else
                {
                    int k = i - L;
                    if(z[k] < R - i + 1)
                        z[i] = z[k];
                    else
                        {
                            L = i;
                            while(R < n && str[R - L] == str[R])
                                ++R;
                            z[i] = R - L;
                            --R;
                        }
                }
        }
    for(int i = 1 ; i < n ; ++i)
        if(z[i] == m && v.size() < DIM)
            v.push_back(i);
    fout << v.size() << '\n';
    int N = v.size();
    N = min(N , DIM);
    for(int i = 0 ; i < N ; ++i)
        fout << v[i] - m - 1 << " ";
}