Cod sursa(job #2868880)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 11 martie 2022 11:18:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;

const int NMAX(2000005);
char a[NMAX], b[NMAX];
int pi[NMAX];

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

    int n = strlen(a + 1);
    int 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);
            if(vec.size() == 1000)
                break;
            k = pi[k];
        }
    }

    fout << vec.size() << '\n';
    for(auto it: vec)
        fout << it << ' ';
    return 0;
}