Cod sursa(job #2883143)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 1 aprilie 2022 10:51:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;
const int NMAX(2000005);
int pi[NMAX];
char a[NMAX], b[NMAX];

int main()
{
    fin >> (a + 1) >> (b + 1);

    int n = strlen(a + 1), m = strlen(b + 1);
    int k = 0;
    for(int i = 2; i <= n; ++i){
        while(k > 0 && a[i] != a[k + 1])
            k = pi[k];
        if(a[i] == a[k + 1])
            ++k;
        pi[i] = k;
    }

    vector<int> vec;
    k = 0;
    for(int i = 1; i <= m; ++i){
        while(k > 0 && b[i] != a[k + 1])
            k = pi[k];
        if(b[i] == a[k + 1])
            ++k;
        if(k == n){
            vec.push_back(i - n);
            k = pi[k];
        }
    }
    fout << vec.size() << '\n';
    for(int i = 0; i < min((int)vec.size(), 1000); ++i)
        fout << vec[i] << ' ';
    return 0;
}